Re: [Cbor] Implementing float->int numeric reduction

How about calling it “numeric determinism” rather than “numeric reduction”?

> On Aug 15, 2023, at 11:12 AM, Anders Rundgren <anders.rundgren.net@gmail.com> wrote:
> 
> Thanx Laurence, this was interesting. IEEE 754 is pure magic :)
> 
> In my implementations of CBOR.Int in JavaScript I have used 2^53-1 (Number.MAX_SAFE_INTEGER) as the limit because above that number there are (mostly) gaps.

Yes, 53 bits of sigificand in a double.

But note for determinism we all have to do exactly the same thing.

> 2^63 (1152921504606846976.0) is one of those interesting numbers.  However, numeric "reduction" doesn't work particularly well for this number since the integer variant is longer.
> If numeric reduction actually is useful, shouldn't the length of the resulting CBOR also be a part of the equation?

I believe the main purpose is determinism. Every number has only one representation. Sometimes the reduction does result in smaller size, but that’s not the purpose. Numeric reduction is “actually useful” for its determinism.

You are right that we could add a rule that the float/double representation must be used if it is smaller. That would make many big whole numbers half the size. It would always be values UINT32_MAX (which need a 64-bit int) that can be represented in a single-precision float. It would be ones were the right most 41 bits are zero. It would still be deterministic too. It’s probably not too difficult to describe and implement. 

My gut reaction is “no” because it is just the ones were the right-most 41 bits are zero (64 - 23 == 41). It’s not worth it for the complexity and likely confusion.

LL

> 
> Float: fa5f000000
> Integ: 1b8000000000000000
> 
> Anders
> 
> On 2023-08-15 19:38, lgl island-resort.com wrote:
>> I’ve come to understand that all whole integers are precisely representable in IEEE 754. No rounding is needed to convert to CBOR type 0/1.
>> I also figured out that you can look inside IEEE 754 with shifts, masks and a little loop (no float HW or lib) to check if a value is a whole integer.
>> Details:
>> I knew that some numbers like 0.10 couldn't be represented exactly as a float, only something like 0.10000000149. I didn’t know whether all whole integers could be represented exactly. If they couldn’t be represented exactly, rounding would be required and that might not be done exactly the same everywhere. Numeric reduction would be not exactly the same everywhere.
>> Then I read aboutbugs in Intel chips <https://randomascii.wordpress.com/2014/01/27/theres-only-four-billion-floatsso-test-them-all/> that manifest in ceilf(), a candidate function for the whole integer check.
>> I had to look deeper for the confidence that the CPU float instructions would give *exactly* the same result on hundreds of CPUs from Intel, Atmel, Apple, Infineon…
>> Here’s an interesting result -- all you have to do is check that the number of bits used in the significand are less than the exponent!
>> For example take the representation of 3:
>> - The exponent is 1 which means the multiply by 2 (shift by 1)
>> - The significand uses one bit with a value of 1/2  (plus 1 is added)
>> - 1 1/2 multiplied by 2 is 3
>> Or 9:
>> - The exponent is 3 which means multiply by 8 (shift by 3)
>> - The significand uses three bits to just be 1/8 (the bits for 1/2 and 1/4 are 0; plus 1 is always added)
>> - 1 1/8 multiplied by 8 is 9
>> This is a nice explanation of the float format <https://softwareengineering.stackexchange.com/questions/215065/can-anyone-explain-representation-of-float-in-memory>.
>> You can implement this <https://github.com/laurencelundblade/float_reduction>without using floating-point HW or libraries — convert the float bits to a uint32_t and do some shifts, masks and a little loop.
>> This also tells me that all whole integers 1, 2, 3,… UINT32_MAX,... are not like 0.10. They can all be represented exactly in IEEE 754. This is probably by design. That makes me very confident that all the HW/SW that convert to float will do exactly the same thing.
>> Here’s 6 ways to check that a float is a whole integer (also see here <https://stackoverflow.com/questions/5796983/checking-if-float-is-an-integer>):
>>    ceilf(f) == f
>>    floorf(f) == f
>>    rint(f) == f
>>    intnearby(f) == f
>>    cast to int and back to float and see the same value (the compiler uses floating-point HW to implement this)
>>    my method of checking significand bits used relative to the exponent
>> Note that probably the same floating-point HW and SW underlies all the languages on a given platform. You get the same implementation working in C, Rust, Swift, Java, Python...
>> I’ve implemented all of these six and confirmed they give the same result for all single precision float values (there’s only 2^32 of them) on Intel with MacOS. You can get the implementation here <https://github.com/laurencelundblade/float_reduction> and run it on your platform if you want.
>> Testing all the double values takes too long, but they work the same.
>> Ceilf() and floor() compile down to one inline instruction on Intel and are probably the least code.
>> The cast method only works for floats less that UINT32_MAX. This is OK for CBOR numeric reduction, but it is not a universal solution like all the others.
>> Additionally, here’s a good article ondeterminism in floating-point <https://randomascii.wordpress.com/2013/07/16/floating-point-determinism/>.
>> LL
>> _______________________________________________
>> CBOR mailing list
>> CBOR@ietf.org
>> https://www.ietf.org/mailman/listinfo/cbor
> 