PUZZLING MATH PUZZLE

[BigDumbDinosaur]

BigEd wrote:

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.

[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:

Code: Select all

    S × 8200 = OJ × 2 + 8198

and:

Code: Select all

    S × 8200 - 8198 = OJ × 2

and finally:

Code: Select all

     (S × 8200 - 8198)
    ———————————————————  =  OJ
             2

Nothin’ to it!

[barrym95838]

BigDumbDinosaur wrote:

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.

[teamtempest]

Quote:

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

[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.

[BigDumbDinosaur]

gfoot wrote:

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.

[Sheep64]

teamtempest on Mon 11 Apr 2022 wrote:

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.

BigDumbDinosaur on Tue 12 Apr 2022 wrote:

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.

[BigDumbDinosaur]

Sheep64 wrote:

teamtempest on Mon 11 Apr 2022 wrote:

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.