implementation choices

[tbreloff]

I'm adding this issue as a holding place for discussing details of the implementation. I might put things here as I'm considering them... that way people can jump in and tell me I'm doing something wrong before I spend too much time on it...

[tbreloff]

I'm redesigning from my initial code to effectively represent unums similar to floats/ints in julia... using bitstypes:

# B is the base of the exponent, E is the number of bits in the exponent
bitstype 64 FixedUnum64{B,E} <: AbstractUnum{B,E}
typealias BinaryUnum64{E}   FixedUnum64{2, E}
typealias DecimalUnum64{E}  FixedUnum64{10, E}
typealias IntUnum64         FixedUnum64{2,1}
typealias Unum64            BinaryUnum64{15}

This brings up a few issues that I'm working through, partially that some functions cannot be staged... there needs to be a slight bootstrap process to be able to generate the unumConstants that will be used in the staged functions.

Assuming I can work through those issues, I'll need to add some extra definitions (which I can generate on a "per-size" basis) since I won't be able to pass through the UInt definitions as I was doing before. The benefit is that it should be nicer to work with these on the bit level... I can do bitwise-or on 2 unums of the same type, for example.

[tbreloff]

Based on discussion in issue #1, I decided to add back the esize/fsize fields and move the signbit back to the left, to match the book. This should be easy enough to change in the future... most of the work goes into changing the unumConstants and show methods. Also I changed the parameters of the types to more closely match the "environment" from the Mathematica prototype.

Types:

abstract AbstractUnum{B,ESS,FSS} <: Real

# B is the base of the exponent
# ESS is the "exponent size size"
# FSS is the "fraction size size"
bitstype 64 FixedUnum64{B,ESS,FSS} <: AbstractUnum{B,ESS,FSS}
typealias BinaryUnum64{ESS,FSS}   FixedUnum64{2,ESS,FSS}
typealias DecimalUnum64{ESS,FSS}  FixedUnum64{10,ESS,FSS}
typealias Unum64                  BinaryUnum64{4,5}

[ScottPJones]

Should the ESS/FSS change, for a particular size of AbstractUnum? I.e. if you want to allow for similar ranges of exponents as IEEE, then you'd need exponent max bits = 5 for 16 bit, 8 for 32 bit, 11 for 64 bit, 15 for 128 bit, so ESS = 3 for 16 bit and 32 bit, 4 for 64 bit and 128 bit (@johnlgustafson, is that correct)?

and for decimal: exponent max bits = 8 for 32 bit, 10 for 64 bit, 14 for 128 bits => 3 for 32 bit, 4 for 64 & 128 bit.

I haven't figured out the max need for the FSS for each fixed size. I'm sure I'm just duplicating what's already in the book :disappointed:

I think this should be: typealias BinaryUnum64 FixedUnum64{2,4,?} typealias DecimalUnum64 FixedUnum64{10,4,?}

edit: easy to confuse myself between the max bits for exp. and fraction, and the bits need to represent that max!

[tbreloff]

For reference regarding the standard floats:

julia> nbitsneeded(x) = (for i in 0:10; if 2^i >= x; return i; end; end; error())
nbitsneeded (generic function with 1 method)

julia> for (n,e) in [(16,5), (32,8), (64,11), (128,14)]
           f = n-e-1
           ess = nbitsneeded(e)
           fss = nbitsneeded(f)
           utagsize = 1 + ess + fss
           minunumbits = utagsize + 3
           maxunumbits = utagsize + 1 + 2^ess + 2^fss
           println("$n bits, $e exponent bits, $f fraction bits. Need $ess for exponent and $fss for fraction. Unum bits range from $minunumbits to $maxunumbits")
       end
16 bits, 5 exponent bits, 10 fraction bits. Need 3 for exponent and 4 for fraction. Unum bits range from 11 to 33
32 bits, 8 exponent bits, 23 fraction bits. Need 3 for exponent and 5 for fraction. Unum bits range from 12 to 50
64 bits, 11 exponent bits, 52 fraction bits. Need 4 for exponent and 6 for fraction. Unum bits range from 14 to 92
128 bits, 14 exponent bits, 113 fraction bits. Need 4 for exponent and 7 for fraction. Unum bits range from 15 to 157

I think we can get away with allowing "large" unums such as {4,6} in a 16bit, 32-bit or 64-bit type, even though the max size is 92 bits. Say we want to enclose Float64 (i.e. create a superset of Float64's values)... then we could create `u = zero(BinaryUnum16{4,6})'. We have enough bits to represent this number. If we do an operation which requires more than 16 bits, we can automatically promote the value to the smallest bitsize containing the number. Example:

u = zero(BinaryUnum16{4,6})
x = one(BinaryUnum32{4,6})
z = u + x # z should be a BinaryUnum32{4,6}

Likewise if we are adding 2 different ESS/FSS combos, we should probably promote the answer to the bigger of each:

u = BinaryUnum64{3,6}(0)
x = BinaryUnum64{4,5}(0)
z = u + x  # z should be BinaryUnum64{4,6}(0)

@johnlgustafson... anything wrong with this logic?

[ScottPJones]

If I understood what @JohnLGustafson was say saying, the ubit took the place of the last fraction bit in a "standard" float, but that seems to make things more difficult, because the ubit would move around, depending on the actual exp. and fraction size. (I have to get time to finish reading the bloody book!)

If you allow 4,6, in a 16-bit unum, don't you only have 4 bits left for both fraction and exponent? I'm also wondering, why is the both the exp. size and frac. size field needed in a fixed length unum (must be my stupidity!). 16-bits - 1 sign - 1 ubit - 4 frac size == 10 bits. If the frac size can encode 1-16 (of course, 10-16 would not be possible), that would leave: 1 -> 9 bits left for exponent, ... 9 -> 1 bit for exponent.

I understand that the variable fraction size is important to keep track of the accuracy, but what does the variable length exponent give? (this is only works when you have a fixed size unum, I think).

[JohnLGustafson]

Unum math takes some getting used to.

Everyone seems to want to pin down the variable-sized quantities to make things easier, the same way hardware engineers do. I sympathize with a lot of this, but if you go to far, you lose the essence that makes the approach work. If you are limiting the unpacked unums to 16, 32, and 64 bits long, then you also need to tie that to a maximum environment. I remember working out that for 64 bits the optimum environment seemed to be {4,5} (lots of exponent, about ten decimals of fraction precision). For 32 bits, you can do up to {3,3}, or give up on the "revealed bit" in the unpacking and then {2,4} is probably a better environment since having only 2^3 = 8 bits for the fraction is pretty cramped.

I hadn't thought about what the maximum for a 16-bit unpacked unum should be. Hmm... It looks like {1,2} or {2,1} have a maximum total size of 11 bits, which allows 5 summary bits. The need for summary bits goes down when the fields being summarized are so short; their main benefit is when you have to build an AND tree to check all 32 or 64 bits of a number. So it might be reasonable to go as high as {2,2} and have a maximum size of 14 bits, which still lets you summarize things like ±oo or NaN operands.

Trying to put a {4,6} environment into a 16-bit unum is crazy, though.

On Aug 3, 2015, at 7:06 AM, Scott P. Jones notifications@github.com wrote:

If I understood what @JohnLGustafson https://github.com/JohnLGustafson was say saying, the ubit took the place of the last fraction bit in a "standard" float, but that seems to make things more difficult, because the ubit would move around, depending on the actual exp. and fraction size. (I have to get time to finish reading the bloody book!)

If you allow 4,6, in a 16-bit unum, don't you only have 4 bits left for both fraction and exponent? I'm also wondering, why is the both the exp. size and frac. size field needed in a fixed length unum (must be my stupidity!). 16-bits - 1 sign - 1 ubit - 4 frac size == 10 bits. If the frac size can encode 1-16 (of course, 10-16 would not be possible), that would leave: 1 -> 9 bits left for exponent, ... 9 -> 1 bit for exponent.

I understand that the variable fraction size is important to keep track of the accuracy, but what does the variable length exponent give? (this is only works when you have a fixed size unum, I think).

— Reply to this email directly or view it on GitHub https://github.com/tbreloff/Unums.jl/issues/3#issuecomment-127253365.

[tbreloff]

Maybe this will help... suppose this is the representation of zero for a {4,5} environment:

julia> c.zero
bits: 0000000000000000000000000000000000000000000000000000000000000000
|    0    | 0000000000000000 | 00000000000000000000000000000000 |  0   |  0000   |  00000  | 
| signbit |       exp        |               frac               | ubit | esize-1 | fsize-1 | 

Then you know that the number of 1's in the exponent will never exceed 1, and the number of 1's in the fraction will never exceed 1, so you can equivalently represent this number with 1 + 1 + 1 + 1 + 4 + 5 = 13 bits (by chopping off most of the bits in the exponent and fraction. Since we only need 13 bits, we could use a 16-bit julia bitstype to represent this number.

Now lets say we have a unum in a {4,5} environment representing the number 0.001953125 (please correct me if I did this math wrong... it was by hand):

julia> Unums.u2float(2., 4, 5, 0, 16)
0.001953125

julia> u
bits: 0000000000000000000000000000000000000000000000000100000000000100
|    0    | 0000000000000000 | 00000000000000000000000000010000 |  0   |  0000   |  00100  | 
| signbit |       exp        |               frac               | ubit | esize-1 | fsize-1 | 

You'll see that fsize is 5, so we need 1 + 1 + 5 + 1 + 4 + 5 = 17 bits to represent this number. We would need a 32-bit julia bitstype to represent this number.

The idea is that, if we know there will be lots of leading zeros in the exponent and fraction, we can store the number in a smaller bitstype.

However, I'm not entirely convinced the method described above is better than either:

• Don't commit to fully representing classic floats (if we can't represent exactly, set the ubit) so we can fix the sizes more consistently, or
• Using 128-bit unums to represent Float64 all the time, etc.

The generated code would likely be much faster if the bits are always in the same place.

[ScottPJones]

@johnlgustafson Maybe you should think separately about my comments on format, because I'm wanting to come up with a more compact storage for unums in database records, not necessarily the best format for computation (which Tom is doing), which is why I'm interested in whether the current exponent size conveys any information that needs to be retained (am I correct that the current fraction size is needed to keep track of the accuracy, along with the ubit?)

[tbreloff]

@ScottPJones: So that we don't hijack this conversation with decimal unums, please see issue #4 that I created, and lets discuss possible decimal unum representations there.

[tbreloff]

@JohnLGustafson: I'm very curious on your thoughts from my last post, as this decision makes a big difference in implementation, and I'll likely want to commit to one or the other.

Assuming I'm using julia bitstypes as the underlying type, and also assuming that I can highly optimize operations if the exponent and fraction positions are fixed, then is it acceptable to put a {ESS,FSS} environment into the smallest bitstype that will fit "negative infinity"?

In this case, a {4,5} or {5,4} environment would be the standard for a 64-bit container, but that would NOT perfectly replicate a 64-bit float. We'd need a 128-bit container for that. Do we think this is acceptable (considering the gains in simplicity and optimizations)?

[ScottPJones]

@tbreloff I didn't even mention decimal unums in my last few messages, good that you've opened #4! I just want to take whatever you come up with, and be able to pack it as tight as possible, without losing any information, thinking about storing millions and millions of these things in the database. John is fighting the "Memory Wall" with unums, but there is still a "Disk Wall" (even for SSDs).

[tbreloff]

You're right... I thought you were implicitly talking about decimal unums since you were talking about database storage.

As for compression (which is what you were asking about): yes the esize and fsize fields are important as they are part of the definition of what that number represents (see p. 48 of the book). I do think you could compress leading zeros of the esize and fsize fields, as well as unused space between signbit and ubit.

Example: You have a unum{4,5}:

julia> mask(7,2) | mask(2,2) | mask(14,1) | mask(46,1)
bits: 0000000000000000001000000000000000000000000000000010000001100011
|    0    | 0000000000001000 | 00000000000000000000000000001000 |  0   |  0011   |  00011  | 
| signbit |       exp        |               frac               | ubit | esize-1 | fsize-1 | 

I think you could compress that to the 14 bits:

| 0 | 1000 | 1000 | 0 | 11 | 11 |

which is the same number in a {2,2} environment.

Note you may need to keep enough metadata around so that you know this is a {2,2} unum... otherwise you will have tough time comparing, for example, a {3,1} unum vs a {1,3} unum...

Note also that this is effectively what I was discussing up above (but doing it within calculations, not just during serialization).

@JohnLGustafson... please correct me if I'm wrong about any of this!!