21–30 of 63 posts
Does anyone know how LibBF stacks up against GMP? [5]
[3] https://bellard.org/jslinux/
[5] https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithme...
For those that don't know, Fabrice Bellard is the author of ffmpeg [1], the tiny c compiler (tcc) [2], linux in the browser [3] among many others [4]. Does anyone know how LibBF stacks up against GMP? [5] [1] http://ffmpeg.org/ [2] https://bellard.org/tcc/ [3] https://bellard.org/jslinux/ [4] https://bellard.org/ [5] https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithme...
For those that don't know, Fabrice Bellard is the author of ffmpeg [1], the tiny c compiler (tcc) [2], linux in the browser [3] among many others [4]. Does anyone know how LibBF stacks up against GMP? [5] [1] http://ffmpeg.org/ [2] https://bellard.org/tcc/ [3] https://bellard.org/jslinux/ [4] https://bellard.org/ [5] https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithme...
Earlier quoted context omitted.
Why does jq need arbitrary precision floating-point numbers?
Because JSON's spec defines a "number" as an arbitrary-precision floating point number, no limit on how many digits can be before or after the decimal or on what positive or negative integers you can put after the "e". Despite the name "JavaScript Object Notation," it does not inherit JavaScript's traditional interpretation that a "number" is an IEEE 754 double. (JSON also does not permit infinities or NaN, which Jav…
I thought the best known multiplication algorithms (the ones based on Fourier transforms) for large numbers are a little slower than O(N log(N)). Has something better been found?
> The basic arithmetic operations (addition, subtraction, multiplication, division, square root) have a near linear running time I thought the best known multiplication algorithms (the ones based on Fourier transforms) for large numbers are a little slower than O(N log(N)). Has something better been found?
For those that don't know, Fabrice Bellard is the author of ffmpeg [1], the tiny c compiler (tcc) [2], linux in the browser [3] among many others [4]. Does anyone know how LibBF stacks up against GMP? [5] [1] http://ffmpeg.org/ [2] https://bellard.org/tcc/ [3] https://bellard.org/jslinux/ [4] https://bellard.org/ [5] https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithme...
[6] https://www.qemu.org/
Mostly off topic but maybe this post attracts people who know the answer to a question that I ran into when I implemented a big integer based rational number library some time ago. The decimal representation of a rational number p / q has the general form ± . ( ), for example 41,111,111 / 333,000 equals 123.456(789). Is there an efficient algorithm to determine the lengths of the fractional parts or one that does at…
As you said, this is equivalent to factorisation in terms of complexity. The Wikipedia article[0] on the subject does a good job of summarising the details of this in the section "Other properties of repeatend lengths". For a simple answer, the lengths are bounded above by Euler's totient function [1] (the sum of factors) of the denominator. Any tighter bounds depend on the specific primes in the factorisation. Note…
I still remember that quite well because that was probably the first and only time that I was unable to find someone stating that we do not know any better, and not only the Wikipedia article but everywhere I looked there was no such statement to be found. I eventually gave up after a couple of evenings but it obviously kept stuck somewhere in my mind and that is why I wrote the initial comment.
Mostly off topic but maybe this post attracts people who know the answer to a question that I ran into when I implemented a big integer based rational number library some time ago. The decimal representation of a rational number p / q has the general form ± . ( ), for example 41,111,111 / 333,000 equals 123.456(789). Is there an efficient algorithm to determine the lengths of the fractional parts or one that does at…
The length of the repeated part is the multiplicative order of 10 mod q [1]. Look at the Wikipedia page on repeated decimals and you can see many of the repeated sequences have length (q-1) ((q-1) is phi(q) when q is prime) [2]. There's a SO answer that talks about this [3]. I think I can derive it here, though take it with a grain of salt as I might have screwed something up. Say you have a rational number p / q, an…
[1] https://math.stackexchange.com/questions/837489/algorithms-f...