Page 2 of 2
Re: PUZZLING MATH PUZZLE
Posted: Tue Apr 12, 2022 2:14 am
by BigDumbDinosaur
Maybe this
S = ((OJ + 7) ÷ 8) + ((OJ + 8191) ÷ 8192)
can be rearranged to
S = ((OJ + 7*1024) ÷ 8192) + ((OJ + 8191) ÷ 8192)
in which case
S = (OJ + 7*1024 + OJ + 8191) ÷ 8192
S = (2*OJ + 15*1024) ÷ 8192
and so
8192*S = (2*OJ + 15*1024)
8192*S - 15*1024 = 2*OJ
whence
OJ = 4096*S - 15*512
But it's quite possible the truncating nature of ÷ is going to scupper that.
Or that I've made some other mistake.
I tried it, without success. In studying the rearrangement of the equations...
Code: Select all
S = ((OJ + 7) ÷ 8) + ((OJ + 8191) ÷ 8192)
can be rearranged to
S = ((OJ + 7*1024) ÷ 8192) + ((OJ + 8191) ÷ 8192)
I think that second equation needs to be written as:
Code: Select all
S = (((OJ + 7)*1024) ÷ 8192) + ((OJ + 8191) ÷ 8192)
Beyond that one, things fall apart.
Re: PUZZLING MATH PUZZLE
Posted: Tue Apr 12, 2022 1:42 pm
by BigDumbDinosaur
Well, I cogitated on this some more and came up with the following
Code: Select all
OJ + 7 OJ + 8191
S = ———————— + ———————————
8 8192
Knowing S, I would have to rearrange the above to get OJ. My algebra skills are somewhat rusty, so please look at the following and correct me if I'm wrong.
Rewrite the equation as:
Code: Select all
OJ + 7 + OJ + 8191
S = ————————————————————
8 + 8192
Simplify as:
Code: Select all
OJ × 2 + 8198
S = ———————————————
8200
followed by:
and:
and finally:
Code: Select all
(S × 8200 - 8198)
——————————————————— = OJ
2
Nothin’ to it! 
Re: PUZZLING MATH PUZZLE
Posted: Tue Apr 12, 2022 2:10 pm
by barrym95838
Well, I cogitated on this some more and came up with the following
Code: Select all
OJ + 7 OJ + 8191
S = ———————— + ———————————
8 8192
Knowing
S, I would have to rearrange the above to get
OJ. My algebra skills are somewhat rusty, so please look at the following and correct me if I'm wrong.
Rewrite the equation as:
Code: Select all
OJ + 7 + OJ + 8191
S = ————————————————————
8 + 8192
Uhh ... does the expression "lowest common denominator" ring a bell? It has been repurposed elsewhere, but its original meaning is relevant here.
Re: PUZZLING MATH PUZZLE
Posted: Tue Apr 12, 2022 2:30 pm
by teamtempest
Uhh ... does the expression "lowest common denominator" ring a bell?
I think what barrym is trying to say is that before adding fractions together, they have to have the same denominator. Regardless of how awful the result may look.
In this case:
Code: Select all
OJ + 7 OJ + 8191 OJ + 7 1024 OJ + 8191 1024 OJ + 7168 OJ + 8191 1025 OJ + 15359
S = ______ + _________ = ______ * ____ + _________ = ______________ + _________ = ______________
8 8192 8 1024 8192 8192 8192 8192
Unfortunately 15359 is a prime number, so that's as simple as it's going to get. But you can re-arrange from here:
Code: Select all
8192 * S - 15359
________________ = OJ
1025
Re: PUZZLING MATH PUZZLE
Posted: Tue Apr 12, 2022 4:37 pm
by gfoot
Following on from my last suggestion, I think you can just use:
OJ = ((S*1024)/1025)*8
where / is integer division rounding down. This counts up OB linearly skipping one count out of every 1025, including the first one, and multiplies by 8 to get OJ.
Re: PUZZLING MATH PUZZLE
Posted: Wed Apr 13, 2022 12:39 am
by BigDumbDinosaur
Following on from my last suggestion, I think you can just use:
OJ = ((S*1024)/1025)*8
where / is integer division rounding down. This counts up OB linearly skipping one count out of every 1025, including the first one, and multiplies by 8 to get OJ.
OJ = ((S*1024)/1025)*8 looks to be a winner. I ran it in T’Bred BASIC with a variety of values for S. The answers when reversed to solve for S agree with the original version of S. My test wasn't exhaustive, but gives me enough confidence to rewrite the T’Bred program to run through the full range of storage that a filesystem can have.
Re: PUZZLING MATH PUZZLE
Posted: Wed May 18, 2022 6:41 pm
by Sheep64
Why does the user have to enter anything more than the number of 1K blocks available?
Dynamic allocation of inodes is possible but it adds complexity. It is much easier to specify the maximum number of files when the filing system is created.
The simplest technique for dynamic inode allocation would be a raw block scheme where 28 bits are for block number and three bits are for position within the block. (One bit is unused because this may be interpreted as a negative inode number.) This has several limitations. Most significantly, it doubles RAM usage and BigDumbDinosaur is trying to implement this on a system with less than 128KB RAM. At present, BigDumbDinosaur is cunningly using a bitmap scheme where a zero bit indicates an allocated block. This allows a quick linear scan where any zero byte represents a fully allocated range of eight data blocks. Any non-zero byte represents a partially allocated range or a completely unused range. A dynamic scheme would require one bit for free/used and another bit for data/meta-data. This scheme also creates a filing system limit of 2^28 blocks (2^38 bytes) which is independent of other limits unless larger inode numbers are used. This requires 40 bit, 48 bit or 64 bit inode numbers. This arrangement is also highly resistant to being compacted or optimized.
It is possible to place inodes in a hidden file. However, recovering allocation after a file is deleted requires the implementation a hash within the hidden file or the implementation of sparse files. Or maybe both. Again, this is intended for implementation on a system with less than 128KB RAM.
A fixed allocation of inodes is a really good place to stop and make a tractable implementation.
a minimum filesystem would be minimally useful, as it could, at most, store 30 files, assuming no subdirectories were created.
Acorn DFS has no sub-directories and a 30 file limit. The part that really makes it suck is that every file must be one contiguous range of blocks. This prevents, for example, two files being opened for output. It is otherwise sufferable. Actually, 30 files may be more than sufficient for data logging.
Re: PUZZLING MATH PUZZLE
Posted: Wed May 18, 2022 8:38 pm
by BigDumbDinosaur
Why does the user have to enter anything more than the number of 1K blocks available?
Dynamic allocation of inodes is possible but it adds complexity. It is much easier to specify the maximum number of files when the filing system is created.
Specifying the number of inodes when creating a filesystem is how I’m doing it. It's the same in the ext* filesystems supported by Linux. A static inode array is created and that’s it. If you suddenly decide you want to store more files and you don't have the inodes for it, too bad. You have to offload the files, recreate the filesystem with more inodes and then restore the files.
I have a separate topic going on my filesystem project.