6 ms·

Write your own arbitrary-precision JavaScript math library

63 points by enobrev 6y ago

bern4444 6y ago
More of a comment on the author, I've found his other articles enlightening, useful as both introductions to functional programming ideas and as comprehensive deep dives demonstrating their intuitive nature both in code and contextual application. A lot of the articles in conjunction with some other resources[1][2][3] are great for diving into functional programming (I've watched and read these many times). If you do front end development with React, I highly recommend the following two videos[4][5] with Ryan Florence and Micahel Jackson (devs behind react-router and Remix) on the compositional nature of React components and hooks. The last note I'll add is, once you get into Functional Programming, you start wanting to use `compose` or its counter part, `pipe` everywhere and coding becomes a lot more fun. I'll put a final plug for one of my own posts on how composition manifests in Javascript/React code[6]. [1] https://jrsinclair.com/articles/2019/elegant-error-handling-with-the-js-either-monad/ https://jrsinclair.com/articles/2019/elegant-error-handling-... [2] https://drboolean.gitbooks.io/mostly-adequate-guide-old/content/ch1.html https://drboolean.gitbooks.io/mostly-adequate-guide-old/cont... [3] https://www.youtube.com/watch?v=Nrp_LZ-XGsY https://www.youtube.com/watch?v=Nrp_LZ-XGsY [4] https://www.youtube.com/watch?v=nUzLlHFVXx0 https://www.youtube.com/watch?v=nUzLlHFVXx0 [5] https://www.youtube.com/watch?v=1jWS7cCuUXw https://www.youtube.com/watch?v=1jWS7cCuUXw [6] https://hackernoon.com/forms-of-composition-in-javascript-and-react-5e1c3wsm https://hackernoon.com/forms-of-composition-in-javascript-an...
waffletower 6y ago
Via Clojure... (= (+ 0.1M 0.2M) 0.3M) true Not such a stupid language.
notagoodidea 6y ago
I always been amazed by arbitrary-precision math library like [GMP](https://gmplib.org/ https://gmplib.org/) taking the time to look from time to time in the source code and understand what to build with the functions provided. This article is a nice introduction to the how it works and the author as a great style.
mci 6y ago
If you do not care about speed, you can get not arbitrary-precision (static number of significant digits, set upfront) but exact (dynamic number of significant digits, as large as you wish) results. Under the hood, your expressions will be directed acyclic graphs of lazy generators, each generator coresponding to a mathematical operation or function. Here is a Python library that employs continued fractions to this end: [0]. You can pull successive partial quotients of the result from the root node of the dag. Whenever any node needs more precise input to deliver more precise output, it pulls a partial quotient from its argument(s). Full disclosure: I wrote the original version of the library 13.5 years ago. Here are the slides from my talk about it: [1]. [0] https://github.com/AdamPrzybyla/python-cf https://github.com/AdamPrzybyla/python-cf [1] https://marcinciura.files.wordpress.com/2019/10/cf-slides.pdf https://marcinciura.files.wordpress.com/2019/10/cf-slides.pd...
- ben509 6y ago
  Very cool. I've seen some libraries around for continued fractions, but this is the only one that's reasonably complete.
- enriquto 6y ago
  How do you check if two different acyclic graphs of lazy generators represent the same number? I do not see how this can be possible. Wouldn't that amount to prove a lot of hard math theorems (e.g, riemann hypothesis)?
  - nextaccountic 6y ago
    You are right that it isn't possible. Equality on real numbers is undecidable.
    - enriquto 6y ago
      Thus if you use such a library, a simple line of code like if (x < 1): may halt, trying to compute x to a higher and higher precision?
joshxyz 6y ago
Coo coo coo coo cool Ive always wondered how libraries like big.js works but man it's just unreadable for beginners trying to understand the math behind it
neillyons 6y ago
Slight tangent, but I recently realised that the built in integer type in Python and Erlang support arbitrary-precision arithmetic while the built in integer types in Go don't. In Go each integer type has a maximum value. eg int32 has a max value of 2,147,483,647. You can still perform arbitrary-precision arithmetic in Go but it requires using the math/big library.
- foota 6y ago
  This isn't that surprising to me since go is built for c like performance.
- OskarS 6y ago
  That's the case for almost all programming languages, Python and Erlang (and a few others, like Raku) are the exceptions there. Any language that's made to be at least a little bit performant (C, C++, Rust, Go, Java, C#, and many, many others) works like this.
- leecarraher 6y ago
  I think this may comes down to interpreted vs compiled. Compiled language assumes some hardware instruction that interacts with primitives at some point. Where interpreted languages are using subroutines to deal with every object. So why not have a check if the value is in bounds, and if not, use arbitrary precision.
- marktangotango 6y ago
  Concretely, it’s because an int is generally defined as 4 bytes and with a sign bit the remaining 31 can have values 2^31.
- SloopJon 6y ago
  In Python 2, int and long were separate types, where int was either a 32- or 64-bit signed integer, and long was arbitrary precision. Python 3 unified the types under the name int: https://www.python.org/dev/peps/pep-0237/ https://www.python.org/dev/peps/pep-0237/ This was a nice enhancement with very few drawbacks, but I can see how it wouldn't necessarily be appropriate in Go.
OskarS 6y ago
Fun fact, this works in Raku: > 0.1 + 0.2 == 0.3 True Decimal numbers are rational number types by default in Raku.
ballenf 6y ago
> But alas, we don’t have tail call recursion in V8 or SpiderMonkey yet. (At least, not at the time of writing). That really is disappointing. BTW, a Javascript interpreter with proper tail calls is built in to every Mac, but it's not in the path by default: https://stackoverflow.com/a/61740889/5641202 https://stackoverflow.com/a/61740889/5641202 Just FYI if you want to run recursive Javascript from the command line in MacOS.
ballenf 6y ago
> // Create a new bigint of 10^n. This turns out to be a bit > // faster than multiplying. > function exp10(n) { > return BigInt(`1${[...new Array(n)].map(() => > 0).join("")}`); > } Could we replace the 0 generation code with `'0'.repeat(n)`? Or `Array(n).fill(0).join("")` if old JS engine support is required?
ExcavateGrandMa 6y ago
"hahahaah what a stupid language..." :D
amelius 6y ago
I don't get it. They first show how you can make arbitrary precision rationals. But then they continue with square/cubic/etc root of these rationals, and then they throw the entire idea of arbitrary precision-ness overboard.
CoryOndrejka 6y ago
Fun article, great style. Couldn’t equality and lte be done more simply with a cross multiply?

63 points by enobrev 6y ago

More of a comment on the author, I've found his other articles enlightening, useful as both introductions to functional programming ideas and as comprehensive deep dives demonstrating their intuitive nature both in code and contextual application. A lot of the articles in conjunction with some other resources[1][2][3] are great for diving into functional programming (I've watched and read these many times). If you do front end development with React, I highly recommend the following two videos[4][5] with Ryan Florence and Micahel Jackson (devs behind react-router and Remix) on the compositional nature of React components and hooks. The last note I'll add is, once you get into Functional Programming, you start wanting to use `compose` or its counter part, `pipe` everywhere and coding becomes a lot more fun. I'll put a final plug for one of my own posts on how composition manifests in Javascript/React code[6]. [1] https://jrsinclair.com/articles/2019/elegant-error-handling-with-the-js-either-monad/ https://jrsinclair.com/articles/2019/elegant-error-handling-... [2] https://drboolean.gitbooks.io/mostly-adequate-guide-old/content/ch1.html https://drboolean.gitbooks.io/mostly-adequate-guide-old/cont... [3] https://www.youtube.com/watch?v=Nrp_LZ-XGsY https://www.youtube.com/watch?v=Nrp_LZ-XGsY [4] https://www.youtube.com/watch?v=nUzLlHFVXx0 https://www.youtube.com/watch?v=nUzLlHFVXx0 [5] https://www.youtube.com/watch?v=1jWS7cCuUXw https://www.youtube.com/watch?v=1jWS7cCuUXw [6] https://hackernoon.com/forms-of-composition-in-javascript-and-react-5e1c3wsm https://hackernoon.com/forms-of-composition-in-javascript-an...

waffletower 6y ago

Via Clojure... (= (+ 0.1M 0.2M) 0.3M) true Not such a stupid language.

notagoodidea 6y ago

I always been amazed by arbitrary-precision math library like [GMP](https://gmplib.org/ https://gmplib.org/) taking the time to look from time to time in the source code and understand what to build with the functions provided. This article is a nice introduction to the how it works and the author as a great style.

mci 6y ago

If you do not care about speed, you can get not arbitrary-precision (static number of significant digits, set upfront) but exact (dynamic number of significant digits, as large as you wish) results. Under the hood, your expressions will be directed acyclic graphs of lazy generators, each generator coresponding to a mathematical operation or function. Here is a Python library that employs continued fractions to this end: [0]. You can pull successive partial quotients of the result from the root node of the dag. Whenever any node needs more precise input to deliver more precise output, it pulls a partial quotient from its argument(s). Full disclosure: I wrote the original version of the library 13.5 years ago. Here are the slides from my talk about it: [1]. [0] https://github.com/AdamPrzybyla/python-cf https://github.com/AdamPrzybyla/python-cf [1] https://marcinciura.files.wordpress.com/2019/10/cf-slides.pdf https://marcinciura.files.wordpress.com/2019/10/cf-slides.pd...

ben509 6y ago
Very cool. I've seen some libraries around for continued fractions, but this is the only one that's reasonably complete.
enriquto 6y ago
How do you check if two different acyclic graphs of lazy generators represent the same number? I do not see how this can be possible. Wouldn't that amount to prove a lot of hard math theorems (e.g, riemann hypothesis)?
- nextaccountic 6y ago
  You are right that it isn't possible. Equality on real numbers is undecidable.
  - enriquto 6y ago
    Thus if you use such a library, a simple line of code like if (x < 1): may halt, trying to compute x to a higher and higher precision?

joshxyz 6y ago

Coo coo coo coo cool Ive always wondered how libraries like big.js works but man it's just unreadable for beginners trying to understand the math behind it

neillyons 6y ago

Slight tangent, but I recently realised that the built in integer type in Python and Erlang support arbitrary-precision arithmetic while the built in integer types in Go don't. In Go each integer type has a maximum value. eg int32 has a max value of 2,147,483,647. You can still perform arbitrary-precision arithmetic in Go but it requires using the math/big library.

foota 6y ago
This isn't that surprising to me since go is built for c like performance.
OskarS 6y ago
That's the case for almost all programming languages, Python and Erlang (and a few others, like Raku) are the exceptions there. Any language that's made to be at least a little bit performant (C, C++, Rust, Go, Java, C#, and many, many others) works like this.
leecarraher 6y ago
I think this may comes down to interpreted vs compiled. Compiled language assumes some hardware instruction that interacts with primitives at some point. Where interpreted languages are using subroutines to deal with every object. So why not have a check if the value is in bounds, and if not, use arbitrary precision.
marktangotango 6y ago
Concretely, it’s because an int is generally defined as 4 bytes and with a sign bit the remaining 31 can have values 2^31.
SloopJon 6y ago
In Python 2, int and long were separate types, where int was either a 32- or 64-bit signed integer, and long was arbitrary precision. Python 3 unified the types under the name int: https://www.python.org/dev/peps/pep-0237/ https://www.python.org/dev/peps/pep-0237/ This was a nice enhancement with very few drawbacks, but I can see how it wouldn't necessarily be appropriate in Go.

OskarS 6y ago

Fun fact, this works in Raku: > 0.1 + 0.2 == 0.3 True Decimal numbers are rational number types by default in Raku.

ballenf 6y ago

> But alas, we don’t have tail call recursion in V8 or SpiderMonkey yet. (At least, not at the time of writing). That really is disappointing. BTW, a Javascript interpreter with proper tail calls is built in to every Mac, but it's not in the path by default: https://stackoverflow.com/a/61740889/5641202 https://stackoverflow.com/a/61740889/5641202 Just FYI if you want to run recursive Javascript from the command line in MacOS.

ballenf 6y ago

> // Create a new bigint of 10^n. This turns out to be a bit > // faster than multiplying. > function exp10(n) { > return BigInt(`1${[...new Array(n)].map(() => > 0).join("")}`); > } Could we replace the 0 generation code with `'0'.repeat(n)`? Or `Array(n).fill(0).join("")` if old JS engine support is required?

ExcavateGrandMa 6y ago

"hahahaah what a stupid language..." :D

amelius 6y ago

I don't get it. They first show how you can make arbitrary precision rationals. But then they continue with square/cubic/etc root of these rationals, and then they throw the entire idea of arbitrary precision-ness overboard.

CoryOndrejka 6y ago

Fun article, great style. Couldn’t equality and lte be done more simply with a cross multiply?