6 ms·

I remember that many years ago, when floating point computation was expensive for Intel CPUs to do, there were multiple ways that programmers used integer trick

I remember that many years ago, when floating point computation was expensive for Intel CPUs to do, there were multiple ways that programmers used integer trickery to work around this. Chuck Moore of Forth fame demonstrated taking the value, say 1.6 multiplied by 4.1 and doing all the intermediate calculations via integers (16 * 41) and then formatting the output by putting the decimal point back in the "right place"; this worked as long as the range of floating point values was within a range that multiplying by 10 didn't exceed 65536 (16 bit integers), for instance. For embedded chips where for instance, you have an analog reading with 10 bits precision to quickly compute multiple times per second, this worked well. I also recall talking many years ago with a Microsoft engineer who had worked with the Microsoft Streets and Trips program (https://archive.org/details/3135521376_qq_CD1 https://archive.org/details/3135521376_qq_CD1 for a screenshot) and that they too had managed to fit what would normally be floating point numbers and the needed calculations into some kind of packed integer format with only the precision that was actually needed, that was faster on the CPUs of the day as well as more easily compressed to fit on the CDROM.

candiddevmike 2y ago
AFAIK this is still the best way to handle money/financial numbers.
- amanda99 2y ago
  That's got nothing to do with perf tho.
  - Maxatar 2y ago
    Nothing to do with perf is a strong claim. If you genuinely don't care about performance you can use an arbitrary-precision rational number representation. But performance often matters, so you trade off precision for performance. I think people are wrong to dismiss floating point numbers in favor of fixed point arithmetic, and I've seen plenty of fixed point arithmetic that has failed spectacularly because people think if you use it, it magically solves all your problems... Whatever approach you take other than going all in with arbitrary precision fractions, you will need to have a good fundamental understanding of your representation and its trade-offs. For me personally I use floating point binary and adjust the decimal point so I can exactly represent any value to 6 decimal places. It's a good trade-off between performance, flexibility, and precision. It's also what the main Bitcoin implementation uses.
    - fluoridation 2y ago
      Huh? Bitcoin uses integers. The maximum supply of BTC in satoshis fits in 64 bits. JS implementations that need to handle BTC amounts use doubles, but only by necessity, since JS doesn't have an integer type. They still use the units to represent satoshis, which works because the maximum supply also fits in 53 bits, so effectively they're also using integers. Anyone who uses binary floating point operations on monetary values doesn't know what they're doing and is asking for trouble.
      - wbl 2y ago
        So if I want to price a barrier in Bermudan rainbow via Monte Carlo I should take the speed hit for a few oddball double rounding problems that are pennies?
        fluoridation 2y ago
        I mean, you do you. People generally don't complain if you're a couple hundred nanoseconds (if that) late. They do complain if your accounts don't add up by a single penny.
        wbl 2y ago
        The quoting of something exotic like this is not well defined to the penny. It's transactions where people really care about pennies.
dwattttt 2y ago
That particular trick is known as fixed point arithmetic (not to be confused with a fixed point of a function)
asadalt 2y ago
this is still true for many embedded projects. like pi pico (2040) uses a table.
dajoh 2y ago
What you're describing is called fixed point arithmetic, a super cool technique I wish more programmers knew about. Proper finance related code should use it, but in my experience in that industry it doesn't seem very common unless you're running mainframes. Funnily enough, I've seen a lot more fixed point arithmetic in software rasterizers than anywhere else. FreeType, GDI, WPF, WARP (D3D11 reference rasterizer) all use it heavily.
- kccqzy 2y ago
  I have worked on firmware that has plenty of fixed point arithmetic. The firmware usually runs on processors without hardware floating point units. For example certain Tesla ECUs use 32-bit integers where they divide it into four bits of integer part and 28 bits of fractional part. So values are scaled by 2^28.
  - phkahler 2y ago
    >> The firmware usually runs on processors without hardware floating point units. I'm working on control code one an ARM cortex-M4f. I wrote it all in fixed point because I don't trust an FPU to be faster, and I also like to have a 32bit accumulator instead of 24bit. I recently converted it all to floating point since we have the M4f part (f indicate FPU), and it's a little slower now. I did get to remove some limit checking since I can rely on the calculations being inside the limits but it's still a little slower than my fixed point implementation.
    - sitkack 2y ago
      The other great thing about going fixed point is that it doesn't expose you to device specific floating point bugs, making your embedded code way more portable and easier to test. 32b float on your embedded device doesn't necessary match your 32b float running on your dev machine.
      - bobmcnamara 2y ago
        32b float can match your desktop. Really just takes a few compiler flags(like avoiding -funsafe-math), setting rounding modes, and not using the 80bit Intel mode(largely disused after 64bit transition).
andrewla 2y ago
I recall playing with FRACTINT, which was a fractal generator that existed before floating point coprocessors were common, that used fixed point math to calculate and display fractals. That was back when fractals were super cool and everyone wanted to be in the business of fractals, and all the Nobel Prizes were given out to fractal researchers.
kragen 2y ago
Sure, FRACTINT is called FRACTINT because it uses fixed-point ("integer") math. And fixed-point math is still standard in Forth; you can do your example in GForth like this: : organize; gforth Gforth 0.7.3, Copyright (C) 1995-2008 Free Software Foundation, Inc. Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license' Type `bye' to exit : %* d>s 10 m*/ ; : %. <# # [char] . hold #s #> type ; ok 1.6 4.1 %* %. 6.5 ok Note that the correct answer is 6.56, so the result 6.5 is incorrectly rounded. Here's how this works. (If you're not familiar with Forth, Forth's syntax is that words are separated by spaces. "ok" is the prompt, ":" defines a subroutine terminated with ";", and you use RPN, passing parameters and receiving results on a stack.) In standard Forth, putting a decimal point in a number makes it a double-precision number, occupying two cells on the stack, and in most Forths the number of digits after the decimal point is stored (until the next number) in the non-standardized variable dpl, decimal point location. Here I've just decided that all my numbers are going to have one decimal place. This means that after a multiplication I need to divide by 10, so I define a subroutine called %* to do this operation. (Addition and subtraction can use the standard d+ and d- subroutines; I didn't implement division, but it would need to pre-multiply the dividend by the scale factor 10.) "%*" is defined in terms of the standard subroutine m*/, which multiplies a double-precision number by a single-precision number and divides the result by a divisor, and the standard subroutine d>s, which converts a double-precision number to a single-precision number. (There's probably a better way to do %*. I'm no Forth expert.) I also need to define a way to print out such numbers, so I define a subroutine called "%.", using Forth's so-called "pictured numeric output", which prints out an unsigned double-precision number inserting a decimal point in the right place with "hold", after printing out the least significant digit. (In PNO we write the format backwards, starting from the least significant digit.) The call to "type" types out the formatted number from the hold space used by PNO. Then I invoked %* on 1.6 and 4.1 and %. on its result, and it printed out 6.5 before giving me the "ok" prompt. If you want to adapt this to use two decimal places: : %* d>s 100 m*/ ; : %. <# # # [char] . hold #s #> type ; redefined %* redefined %. ok 1.60 4.10 %* %. 6.56 ok Note, however, that a fixed-point multiplication still involves a multiplication, requiring potentially many additions, not just an addition. The paper, which I haven't read yet, is about how to approximate a floating-point multiplication by using an addition, presumably because in multiplication you add the mantissas, or maybe using a table of logarithms. Forth's approach to decimal numbers was a clever hack for the 01970s and 01980s on sub-MIPS machines with 8-bit and 16-bit ALUs, where you didn't want to be invoking 32-bit arithmetic casually, and you didn't have floating-point hardware. Probably on 32-bit machines it was already the wrong approach (a double-precision number on a 32-bit Forth is 64 bits, which is about 19 decimal digits) and clearly it is on 64-bit machines, where you don't even get out of the first 64-bit word until that many digits: 0 1 %. 184467440737095516.16 ok GForth and other modern standard Forths do support floating-point, but for backward compatibility, they treat input with decimal points as double-precision integers.
touisteur 2y ago
Ozaki has been doing fp64 matrix-multiplication using int8 tensor cores https://arxiv.org/html/2306.11975v4 https://arxiv.org/html/2306.11975v4 Interesting AF.

candiddevmike 2y ago

AFAIK this is still the best way to handle money/financial numbers.

amanda99 2y ago
That's got nothing to do with perf tho.
- Maxatar 2y ago
  Nothing to do with perf is a strong claim. If you genuinely don't care about performance you can use an arbitrary-precision rational number representation. But performance often matters, so you trade off precision for performance. I think people are wrong to dismiss floating point numbers in favor of fixed point arithmetic, and I've seen plenty of fixed point arithmetic that has failed spectacularly because people think if you use it, it magically solves all your problems... Whatever approach you take other than going all in with arbitrary precision fractions, you will need to have a good fundamental understanding of your representation and its trade-offs. For me personally I use floating point binary and adjust the decimal point so I can exactly represent any value to 6 decimal places. It's a good trade-off between performance, flexibility, and precision. It's also what the main Bitcoin implementation uses.
  - fluoridation 2y ago
    Huh? Bitcoin uses integers. The maximum supply of BTC in satoshis fits in 64 bits. JS implementations that need to handle BTC amounts use doubles, but only by necessity, since JS doesn't have an integer type. They still use the units to represent satoshis, which works because the maximum supply also fits in 53 bits, so effectively they're also using integers. Anyone who uses binary floating point operations on monetary values doesn't know what they're doing and is asking for trouble.
    - wbl 2y ago
      So if I want to price a barrier in Bermudan rainbow via Monte Carlo I should take the speed hit for a few oddball double rounding problems that are pennies?
      - fluoridation 2y ago
        I mean, you do you. People generally don't complain if you're a couple hundred nanoseconds (if that) late. They do complain if your accounts don't add up by a single penny.
        wbl 2y ago
        The quoting of something exotic like this is not well defined to the penny. It's transactions where people really care about pennies.

dwattttt 2y ago

That particular trick is known as fixed point arithmetic (not to be confused with a fixed point of a function)

asadalt 2y ago

this is still true for many embedded projects. like pi pico (2040) uses a table.

dajoh 2y ago

What you're describing is called fixed point arithmetic, a super cool technique I wish more programmers knew about. Proper finance related code should use it, but in my experience in that industry it doesn't seem very common unless you're running mainframes. Funnily enough, I've seen a lot more fixed point arithmetic in software rasterizers than anywhere else. FreeType, GDI, WPF, WARP (D3D11 reference rasterizer) all use it heavily.

kccqzy 2y ago
I have worked on firmware that has plenty of fixed point arithmetic. The firmware usually runs on processors without hardware floating point units. For example certain Tesla ECUs use 32-bit integers where they divide it into four bits of integer part and 28 bits of fractional part. So values are scaled by 2^28.
- phkahler 2y ago
  >> The firmware usually runs on processors without hardware floating point units. I'm working on control code one an ARM cortex-M4f. I wrote it all in fixed point because I don't trust an FPU to be faster, and I also like to have a 32bit accumulator instead of 24bit. I recently converted it all to floating point since we have the M4f part (f indicate FPU), and it's a little slower now. I did get to remove some limit checking since I can rely on the calculations being inside the limits but it's still a little slower than my fixed point implementation.
  - sitkack 2y ago
    The other great thing about going fixed point is that it doesn't expose you to device specific floating point bugs, making your embedded code way more portable and easier to test. 32b float on your embedded device doesn't necessary match your 32b float running on your dev machine.
    - bobmcnamara 2y ago
      32b float can match your desktop. Really just takes a few compiler flags(like avoiding -funsafe-math), setting rounding modes, and not using the 80bit Intel mode(largely disused after 64bit transition).

andrewla 2y ago

I recall playing with FRACTINT, which was a fractal generator that existed before floating point coprocessors were common, that used fixed point math to calculate and display fractals. That was back when fractals were super cool and everyone wanted to be in the business of fractals, and all the Nobel Prizes were given out to fractal researchers.

kragen 2y ago

Sure, FRACTINT is called FRACTINT because it uses fixed-point ("integer") math. And fixed-point math is still standard in Forth; you can do your example in GForth like this: : organize; gforth Gforth 0.7.3, Copyright (C) 1995-2008 Free Software Foundation, Inc. Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license' Type `bye' to exit : %* d>s 10 m*/ ; : %. <# # [char] . hold #s #> type ; ok 1.6 4.1 %* %. 6.5 ok Note that the correct answer is 6.56, so the result 6.5 is incorrectly rounded. Here's how this works. (If you're not familiar with Forth, Forth's syntax is that words are separated by spaces. "ok" is the prompt, ":" defines a subroutine terminated with ";", and you use RPN, passing parameters and receiving results on a stack.) In standard Forth, putting a decimal point in a number makes it a double-precision number, occupying two cells on the stack, and in most Forths the number of digits after the decimal point is stored (until the next number) in the non-standardized variable dpl, decimal point location. Here I've just decided that all my numbers are going to have one decimal place. This means that after a multiplication I need to divide by 10, so I define a subroutine called %* to do this operation. (Addition and subtraction can use the standard d+ and d- subroutines; I didn't implement division, but it would need to pre-multiply the dividend by the scale factor 10.) "%*" is defined in terms of the standard subroutine m*/, which multiplies a double-precision number by a single-precision number and divides the result by a divisor, and the standard subroutine d>s, which converts a double-precision number to a single-precision number. (There's probably a better way to do %*. I'm no Forth expert.) I also need to define a way to print out such numbers, so I define a subroutine called "%.", using Forth's so-called "pictured numeric output", which prints out an unsigned double-precision number inserting a decimal point in the right place with "hold", after printing out the least significant digit. (In PNO we write the format backwards, starting from the least significant digit.) The call to "type" types out the formatted number from the hold space used by PNO. Then I invoked %* on 1.6 and 4.1 and %. on its result, and it printed out 6.5 before giving me the "ok" prompt. If you want to adapt this to use two decimal places: : %* d>s 100 m*/ ; : %. <# # # [char] . hold #s #> type ; redefined %* redefined %. ok 1.60 4.10 %* %. 6.56 ok Note, however, that a fixed-point multiplication still involves a multiplication, requiring potentially many additions, not just an addition. The paper, which I haven't read yet, is about how to approximate a floating-point multiplication by using an addition, presumably because in multiplication you add the mantissas, or maybe using a table of logarithms. Forth's approach to decimal numbers was a clever hack for the 01970s and 01980s on sub-MIPS machines with 8-bit and 16-bit ALUs, where you didn't want to be invoking 32-bit arithmetic casually, and you didn't have floating-point hardware. Probably on 32-bit machines it was already the wrong approach (a double-precision number on a 32-bit Forth is 64 bits, which is about 19 decimal digits) and clearly it is on 64-bit machines, where you don't even get out of the first 64-bit word until that many digits: 0 1 %. 184467440737095516.16 ok GForth and other modern standard Forths do support floating-point, but for backward compatibility, they treat input with decimal points as double-precision integers.

touisteur 2y ago

Ozaki has been doing fp64 matrix-multiplication using int8 tensor cores https://arxiv.org/html/2306.11975v4 https://arxiv.org/html/2306.11975v4 Interesting AF.