This is perfect for jq[0].
LibBF – a small library to handle arbitrary precision floating point numbers
11–20 of 63 posts
Re: LibBF – a small library to handle arbitrary precision floating point numbers
#12Mostly 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…
There are some closely related difficult problems. Consider the fraction a/b, and let r be the length of the repeating fractional part. Then r <= b - 1. Moreover, if r == b - 1, then b is prime. In general, r divides phi(b), where phi is the Euler phi function.
Re: LibBF – a small library to handle arbitrary precision floating point numbers
#13Mostly 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 that Euler's totient function is "always 'nearly n'" in magnitude (Hardy and Littlewood), so that representation will be very expensive for most fractions of large denominator.
[0]: https://en.wikipedia.org/wiki/Repeating_decimal [1]: https://en.wikipedia.org/wiki/Euler%27s_totient_function
Re: LibBF – a small library to handle arbitrary precision floating point numbers
#14For Mac users trying this at home, I made the following changes to build and run the tinypi tests on Sierra: 1. Comment out the malloc.h include in tinypi.c. 2. Add -Wno-unused-function to CFLAGS. 3. Use shasum, rather than sha1sum, in the test target.
Having malloc.h as an include is bizarre, anyway. The standard location for malloc and related functions is stdlib.h, and removing that include should let it still compile on any reasonable platform.
Re: LibBF – a small library to handle arbitrary precision floating point numbers
#15This is perfect for jq[0]. [0] https://github.com/stedolan/jq
...How is it perfect for jq?
Re: LibBF – a small library to handle arbitrary precision floating point numbers
#16This is perfect for jq[0]. [0] https://github.com/stedolan/jq
Why does jq need arbitrary precision floating-point numbers?
Re: LibBF – a small library to handle arbitrary precision floating point numbers
#17Mostly 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…
While I’m sure you know this, when computing the fractional part you will have at most q-1 digits in your repeating cycle. When you divide by q, you have at most q unique remainders (0 to q-1). Also when computing the fractional part, if you end up with the same remainder as you’ve previously seen then you’ve hit the cycle.
That is exactly what I did, I implemented some cycle finding algorithm, a tortoise and hare variant maybe but I can not tell from the top of my head, on the reminder sequence giving up after a user-specified number of steps. But it irks me that this may abort just a hand full of steps before finally finding the cycle.
And unfortunately q is just way to loose as a bound if it even deserves the name bound in this case. I initially started looking into this because I wanted to print something like »0.577 215 664 « but in that case q is essentially useless because you either have to really search the cycle which quickly becomes impractical once q reaches millions or billions or you have to live with »0.577 215 664 «.
Re: LibBF – a small library to handle arbitrary precision floating point numbers
#18Mostly 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, and w.l.o.g., p
p/q = R sum_{k=1}^{\infty} 10^{-s k} = R / ( 10^s - 1 )
p (10^s - 1) - q R = 0
So to make the above equation true, let's be coarse and choose s = phi(q) in the below:
.. p (10^{ phi(q) } - 1 ) - q R = 0
-> p ( C q ) - q R = 0
-> q ( p C - R ) = 0
There's also the case of when 10 and q aren't relatively prime that needs to be worked out.
You can also see how this argument could be modified to work with other bases.
[1] https://softwareengineering.stackexchange.com/a/192077
[2] https://en.wikipedia.org/wiki/Repeating_decimal#Decimal_expa...
Re: LibBF – a small library to handle arbitrary precision floating point numbers
#19This is perfect for jq[0]. [0] https://github.com/stedolan/jq
Why does jq need arbitrary precision floating-point numbers?
not that it's needed, but JSONschema has this kind of crazy part where it lets you do multipleOf for floating point numbers. Of course 2.7 is not a multiple of 0.3 in IEEE-64-bit FP.
Re: LibBF – a small library to handle arbitrary precision floating point numbers
#20This is perfect for jq[0]. [0] https://github.com/stedolan/jq
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 JavaScript does permit.)