3 ms·

Btw: I'm looking for efficient ways to represent numbers of arbitrary precision, and performing mathematical operations on the them. It's for a toy financial ca

by myth2018 2y ago

Btw: I'm looking for efficient ways to represent numbers of arbitrary precision, and performing mathematical operations on the them. It's for a toy financial calculator I'm writing in my spare time. My knowledge is really lacking in this field and I'm not even sure about what I should be asking/searching for. Could someone suggest me some sources? Preferably online, but books would also be very welcome.

deleted 2y ago
[deleted]
kolinko 2y ago
You can check how python does it, and also ask chatgpt - I found it to be very helpful in cases like these.
pavpanchekha 2y ago
The typical library folks use is called MPFR: https://mpfr.org https://mpfr.org It's fast, high quality, and very complete.
- vlovich123 2y ago
  It might be also important to note that mpfr is really for scientific purposes that need to deal with such large precision - there are significant memory and performance costs. For financial accounting applications, a fixed precision floating point library (aka fixed point arithmetic) is probably a better choice. Also mpfr is c/c++ but the author didn’t really specify their language and there may be other better options although bindings likely exist.
  - denton-scratch 2y ago
    I once wrote some accounting software for a tiny team in an investment bank. The bosses decided that we should use our brand-new platform, which was cheap to develop for, because most (normal) things could be done without code. All went well for a couple of months; then the customer reported that the system failed for currency conversions to and from Yen. There wasn't enough precision. We had to write an arbitrary-precision maths library, resulting in the project overrunning budget by a factor of three.
    - vlovich123 2y ago
      There’s a world of difference between an arbitrary precision library like mpfr suited for financial applications, a fixed precision “Decimal” type that’s better suited for financial applications, and trying to roll your own thing. I don’t believe anywhere that I wrote that you should roll your own. All I said is that for financial stuff “Decimal”-like APIs are going to be easier to configure, manage and be better suited for financial applications.
      - denton-scratch 2y ago
        Sure. This was the early eighties; we didn't really have "libraries", and even if we had, there was no way to plug them into this proprietary development system. > library like mpfr suited for financial applications, a fixed precision “Decimal” type that’s better suited for financial applications I don't know mpfr, but my guess is you meant to say that mpfr is better-suited for scientific applications?
        vlovich123 2y ago
        Yeah, arbitrary precision is different from fixed point precision that financial institutions typically need. MPFR is arbitrary precision so if you’re doing stuff involving our solar system and beyond, you probably want to use mpfr and be very careful in setting up the equations you’re using. Financial transactions have different requirements though and the arbitrary precision is unnecessarily slow, uses unnecessary amounts of RAM, and I believe will probably difficult to configure correctly. That being said, I’ve never really used mpfr. More just relaying what I understand to be the lay of the land.
        nullc 2y ago
        MPFR itself is pretty easy to use. Unfortunately, if your formula are ill conditioned you can get inaccurate results even using thousands of bits of precision... so there is no replacement for doing analysis and testing. Perhaps if there were some interval-math equivalent of MPFR you could at least tell when your code might be producing wrong results without extensive mathematical analysis.
- myth2018 2y ago
  Thanks for the suggestion. And do you know where I could read about the underlying theory? I'd like to implement the most I could from scratch, for learning purposes.
  - Galanwe 2y ago
    The underlying theory is primary school math if you stay in a decimal fixed point format. All you have to do is choose the number of decimals you want. Say, half the number of digits of the biggest number that fits your desired size. Half these digits will be for the integral part, the other half for the decimal part. For instance, if you want to store signed fixed point on 32 bits, the highest number in base 10 is 2 billion. That's 9 zeros for you. Say you pick 4 for the decimal part, just multiply your numbers by 10000. So 1 is 10000. You can use all the regular operators you want on these numbers, just remember to x10000 when storing them, and /10000 when extracting from them. You're really just "computing on tenths of thousands" instead of "computing on ones". This is obviously wasteful to do that in a decimal base, but it's also trivial, so unless you cannot afford to lose that many digits, stick with it. When confortable, consider moving to a binary base so that you don't waste as much digits. Note that it is not _stricly_ mandatory to use fixed point numbers when doing financial computations. Floating point can work just fine, it all depends on what kind of number and computation you have to deal with. Typically, the need for fixed point arises when 1) You work with really small and large numbers together, these are the most susceptible to be misrepresented as floating points. The best example is if you need to deal with exchange rates to convert between currencies that have widely different bases. 2) You need to chain a lot of operations, which could compound imprécision. 3) You need to store exact numbers of arbitrary precision (e.g. market data)
    - teo_zero 2y ago
      > You can use all the regular operators you want on these numbers, just remember to x10000 when storing them, and /10000 when extracting from them. ??? You can only use addition and subtraction in this way. As soon as you touch multiplication and division the rules don't hold anymore!
physicsguy 2y ago
For finances, numbers are typically stored as integers, since floating point problems can crop up quite easily if you don't. Some languages can handle arbitrary precision integers out of the box - this is true in Python for e.g., in others then you have to use special libraries to do so. Even when you can represent the numbers, you still have to take care since doing things like calculating interest might lead to floating point numbers which need to be handled.
constantcrying 2y ago
>Btw: I'm looking for efficient ways to represent numbers of arbitrary precision, and performing mathematical operations on the them The easiest way is to look at how fixed length numbers are implemented and extend the ranges of values to arbitrary length. For financial operations it seems likely that you want fixed point arithmetic, which essentially just means you calculate in integers of cents. So you just need to implement arbitrary length integers, which isn't particularly hard I would say. The algorithms you need are the ones you already know from school. Long division and multiplication. (There are better ones though).
tzs 2y ago
For implementing it yourself from scratch for learning it is a good idea to first step back and ask how much precision do you need and how fast does it need to be. Also are we talking about just integers, or do you also want fixed point and/or floating point? If you don't need really huge numbers and you don't need it to be very fast and just need the add, subtract, multiply, and divide (with remainder) on integers there's a decent chance you can write something by just implementing the same algorithms you would use to do it by hand on paper. You To make is easy to debug you could represent an arbitrary integer as an array of base 10 digits, least significant digit first. E.g., the number 123456 would be represented as [6, 5, 4, 3, 2, 1]. Addition and subtraction are pretty straightforward in that representation. Multiplication is more complicated by just follow what you do when you hand multiply and you'll get it. Division is harder but for a project you are doing for learning purposes it is doable. Once you've got those operations you can improve them by changing to a higher base. For example you might switch to base 1000. Then 123456 would be [456, 123]. Assuming the base is small enough that each digit fits in one machine word addition and subtraction are O(n) and multiplication and division as described above are O(n^2) where n is the number of digits in your operands (let's assume equal sized operands). Switching from base 10 to base 1000 cuts the number of digits in your numbers by a factor of 3, speeding up addition and subtraction by a factor of 3 and multiplication and division by a factor of 9. It usually is easy to go up to base whatever fits in half a machine word. For example on a 32-bit processor that would be base 65536. Digits then range from 0 through 65535 and and adding or multiplying a pair of digits will not overflow. You can also go up to the full machine word for your base but that can be more work. So for a 32-bit machine that would be base 4294967295. You then have to deal with overflow which adds a small amount of extra logic for addition/subtraction. For multiplication you need a 32-bit x 32-bit => 64-bit operation. Many 32-bit processors do have that but it might not be exposed in whatever language you are using. The above is all stuff you can probably do without any more theory than you can remember from elementary school. Taking it farther you probably want to do some reading. You can get a decent speedup on multiplication by using the Karatsuba algorithm, which speeds up multiplication from O(n^2) to O(n^1.58). Karatsuba is pretty easy and Wikipedia explains it adequately. An extensive treatment of all of this is in Knuth volume 2. He covers everything from the "do it like you do by hand" up to whatever was state of the art at the time the book was written. I wouldn't necessarily say you should go out and buy Knuth volume 2, but if you can borrow it from a library or someone you know take a look.
denton-scratch 2y ago
> efficient ways to represent numbers of arbitrary precision I used to write COBOL for Burroughs machines, which had hardware BCD arithmetic. It wasn't "arbitrary precision" in the sense that you could input an arbitrary number and get an exact result; you had to allocate storage for each intermediate result, so your program had to be designed to handle some specific amount of precision. I'm sure some Intel microprocessors had BCD hardware; maybe they still do.

deleted 2y ago

[deleted]

kolinko 2y ago

You can check how python does it, and also ask chatgpt - I found it to be very helpful in cases like these.

pavpanchekha 2y ago

The typical library folks use is called MPFR: https://mpfr.org https://mpfr.org It's fast, high quality, and very complete.

vlovich123 2y ago
It might be also important to note that mpfr is really for scientific purposes that need to deal with such large precision - there are significant memory and performance costs. For financial accounting applications, a fixed precision floating point library (aka fixed point arithmetic) is probably a better choice. Also mpfr is c/c++ but the author didn’t really specify their language and there may be other better options although bindings likely exist.
- denton-scratch 2y ago
  I once wrote some accounting software for a tiny team in an investment bank. The bosses decided that we should use our brand-new platform, which was cheap to develop for, because most (normal) things could be done without code. All went well for a couple of months; then the customer reported that the system failed for currency conversions to and from Yen. There wasn't enough precision. We had to write an arbitrary-precision maths library, resulting in the project overrunning budget by a factor of three.
  - vlovich123 2y ago
    There’s a world of difference between an arbitrary precision library like mpfr suited for financial applications, a fixed precision “Decimal” type that’s better suited for financial applications, and trying to roll your own thing. I don’t believe anywhere that I wrote that you should roll your own. All I said is that for financial stuff “Decimal”-like APIs are going to be easier to configure, manage and be better suited for financial applications.
    - denton-scratch 2y ago
      Sure. This was the early eighties; we didn't really have "libraries", and even if we had, there was no way to plug them into this proprietary development system. > library like mpfr suited for financial applications, a fixed precision “Decimal” type that’s better suited for financial applications I don't know mpfr, but my guess is you meant to say that mpfr is better-suited for scientific applications?
      - vlovich123 2y ago
        Yeah, arbitrary precision is different from fixed point precision that financial institutions typically need. MPFR is arbitrary precision so if you’re doing stuff involving our solar system and beyond, you probably want to use mpfr and be very careful in setting up the equations you’re using. Financial transactions have different requirements though and the arbitrary precision is unnecessarily slow, uses unnecessary amounts of RAM, and I believe will probably difficult to configure correctly. That being said, I’ve never really used mpfr. More just relaying what I understand to be the lay of the land.
        nullc 2y ago
        MPFR itself is pretty easy to use. Unfortunately, if your formula are ill conditioned you can get inaccurate results even using thousands of bits of precision... so there is no replacement for doing analysis and testing. Perhaps if there were some interval-math equivalent of MPFR you could at least tell when your code might be producing wrong results without extensive mathematical analysis.
myth2018 2y ago
Thanks for the suggestion. And do you know where I could read about the underlying theory? I'd like to implement the most I could from scratch, for learning purposes.
- Galanwe 2y ago
  The underlying theory is primary school math if you stay in a decimal fixed point format. All you have to do is choose the number of decimals you want. Say, half the number of digits of the biggest number that fits your desired size. Half these digits will be for the integral part, the other half for the decimal part. For instance, if you want to store signed fixed point on 32 bits, the highest number in base 10 is 2 billion. That's 9 zeros for you. Say you pick 4 for the decimal part, just multiply your numbers by 10000. So 1 is 10000. You can use all the regular operators you want on these numbers, just remember to x10000 when storing them, and /10000 when extracting from them. You're really just "computing on tenths of thousands" instead of "computing on ones". This is obviously wasteful to do that in a decimal base, but it's also trivial, so unless you cannot afford to lose that many digits, stick with it. When confortable, consider moving to a binary base so that you don't waste as much digits. Note that it is not _stricly_ mandatory to use fixed point numbers when doing financial computations. Floating point can work just fine, it all depends on what kind of number and computation you have to deal with. Typically, the need for fixed point arises when 1) You work with really small and large numbers together, these are the most susceptible to be misrepresented as floating points. The best example is if you need to deal with exchange rates to convert between currencies that have widely different bases. 2) You need to chain a lot of operations, which could compound imprécision. 3) You need to store exact numbers of arbitrary precision (e.g. market data)
  - teo_zero 2y ago
    > You can use all the regular operators you want on these numbers, just remember to x10000 when storing them, and /10000 when extracting from them. ??? You can only use addition and subtraction in this way. As soon as you touch multiplication and division the rules don't hold anymore!

physicsguy 2y ago

For finances, numbers are typically stored as integers, since floating point problems can crop up quite easily if you don't. Some languages can handle arbitrary precision integers out of the box - this is true in Python for e.g., in others then you have to use special libraries to do so. Even when you can represent the numbers, you still have to take care since doing things like calculating interest might lead to floating point numbers which need to be handled.

constantcrying 2y ago

>Btw: I'm looking for efficient ways to represent numbers of arbitrary precision, and performing mathematical operations on the them The easiest way is to look at how fixed length numbers are implemented and extend the ranges of values to arbitrary length. For financial operations it seems likely that you want fixed point arithmetic, which essentially just means you calculate in integers of cents. So you just need to implement arbitrary length integers, which isn't particularly hard I would say. The algorithms you need are the ones you already know from school. Long division and multiplication. (There are better ones though).

tzs 2y ago

For implementing it yourself from scratch for learning it is a good idea to first step back and ask how much precision do you need and how fast does it need to be. Also are we talking about just integers, or do you also want fixed point and/or floating point? If you don't need really huge numbers and you don't need it to be very fast and just need the add, subtract, multiply, and divide (with remainder) on integers there's a decent chance you can write something by just implementing the same algorithms you would use to do it by hand on paper. You To make is easy to debug you could represent an arbitrary integer as an array of base 10 digits, least significant digit first. E.g., the number 123456 would be represented as [6, 5, 4, 3, 2, 1]. Addition and subtraction are pretty straightforward in that representation. Multiplication is more complicated by just follow what you do when you hand multiply and you'll get it. Division is harder but for a project you are doing for learning purposes it is doable. Once you've got those operations you can improve them by changing to a higher base. For example you might switch to base 1000. Then 123456 would be [456, 123]. Assuming the base is small enough that each digit fits in one machine word addition and subtraction are O(n) and multiplication and division as described above are O(n^2) where n is the number of digits in your operands (let's assume equal sized operands). Switching from base 10 to base 1000 cuts the number of digits in your numbers by a factor of 3, speeding up addition and subtraction by a factor of 3 and multiplication and division by a factor of 9. It usually is easy to go up to base whatever fits in half a machine word. For example on a 32-bit processor that would be base 65536. Digits then range from 0 through 65535 and and adding or multiplying a pair of digits will not overflow. You can also go up to the full machine word for your base but that can be more work. So for a 32-bit machine that would be base 4294967295. You then have to deal with overflow which adds a small amount of extra logic for addition/subtraction. For multiplication you need a 32-bit x 32-bit => 64-bit operation. Many 32-bit processors do have that but it might not be exposed in whatever language you are using. The above is all stuff you can probably do without any more theory than you can remember from elementary school. Taking it farther you probably want to do some reading. You can get a decent speedup on multiplication by using the Karatsuba algorithm, which speeds up multiplication from O(n^2) to O(n^1.58). Karatsuba is pretty easy and Wikipedia explains it adequately. An extensive treatment of all of this is in Knuth volume 2. He covers everything from the "do it like you do by hand" up to whatever was state of the art at the time the book was written. I wouldn't necessarily say you should go out and buy Knuth volume 2, but if you can borrow it from a library or someone you know take a look.

denton-scratch 2y ago

> efficient ways to represent numbers of arbitrary precision I used to write COBOL for Burroughs machines, which had hardware BCD arithmetic. It wasn't "arbitrary precision" in the sense that you could input an arbitrary number and get an exact result; you had to allocate storage for each intermediate result, so your program had to be designed to handle some specific amount of precision. I'm sure some Intel microprocessors had BCD hardware; maybe they still do.