4 ms·

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 li

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 ±<integer part>.<non-repeating fractional part>(<repeating fractional part>), 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 least provides reasonably tight bounds on them? I did quite a bit of research at the time but only with limited success. I am reasonably sure that finding the exact lengths is comparable in hardness to factoring p and q in some cases and possibly harder in the general case. But I did not come across much with regard to bounds on the lengths. Maybe there was somewhere an implicit answer to my question which I did not recognize or fully appreciate due to my limited knowledge of number theory but I never came across an explicit statement that said that printing the decimal representation of a rational number or estimating its length is a hard or unsolved problem. I ended up just performing the expansion digit by digit until I detected a cycle or reached a specified maximum length, but it would by nice to know in advance how long it will be or at least to learn that this is actually an hard or unsolved problem.

tadkar 9y ago
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.
- danbruc 9y ago
  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 <901,532 more digits>« 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 <up to 999,999,991 more digits but maybe also just one>«.
  - thaumasiotes 9y ago
    > 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. What's the cycle finding for? Isn't it enough to record the remainder sequence with indices? As soon as any remainder reoccurs, that's the cycle.
    - danbruc 9y ago
      You could of course just maintain the set of remainders seen so far and then you would detect the cycle by reaching a remainder that is already in your set of remainders seen so far but that requires space proportional to the number of digits expanded and if you are expanding a lot of digits and have a large denominator, this will add substantially to the amount of memory consumed. The digits themselves require of course a linear amount of space, too, but only about one byte per digit compared to the potentially big remainder.
siegelzero 9y ago
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.
mrmr1993 9y ago
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 https://en.wikipedia.org/wiki/Repeating_decimal [1]: https://en.wikipedia.org/wiki/Euler%27s_totient_function https://en.wikipedia.org/wiki/Euler%27s_totient_function
- danbruc 9y ago
  That Wikipedia article on repeating decimals is probably where I started looking into it, but the article is somewhat weird. For many problems Wikipedia articles say we know this and that but those other things are still unknown, this article has a lot of information but does not talk about unknown things at all. The length of the repeating fractional part of 1 / n divides φ(n)...and then nothing. Is this all we know or is there more but just not in this article? 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.
  - jcranmer 9y ago
    MathWorld is often a decent resource for finding this kind of information: <http://mathworld.wolfram.com/DecimalPeriod.html> http://mathworld.wolfram.com/DecimalPeriod.html>, but it's often difficult to arrive at those pages if you don't have any idea where to start.
    - yorwba 9y ago
      There's an extra > at the end of your link.
abetusk 9y ago
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 < q. Consider an integer, R, that corresponds to the repeated portion of the rational number (in base 10), with length s (in decimal). This implies: p/q = R sum_{k=1}^{\infty} 10^{-s k} = R / ( 10^s - 1 ) rearranging terms: p (10^s - 1) - q R = 0 Let's just assume for now 10 and q are relatively prime. I think I have to do a little hand waiving at this point and just assume the above has a solution. If the above is true, this means 10^s = 1 (%q) for s equal to the order of 10 mod q, which is a fancy way of saying 10^s = C q + 1 for some integer C. One choice that will always work is taking s = phi(q) though this might be smaller (specifically a divisor or phi(q)) depending on what the order of 10 is to q. 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 And there you go. Assuming that I haven't bungled anything, this also gives an 'algorithm' to find the actual repeated sequence: R = p C = p 10^{phi(q)} . Choosing s, the length of R in base 10, to be phi(q) will always "work", but, again, s might be able to be chosen smaller, depending on what divisors of phi(q) there are and what order 10 is to q, so the real answer of the length of the repeated sequence is 10's order in the multiplicative group mod q. 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 https://softwareengineering.stackexchange.com/a/192077 [2] https://en.wikipedia.org/wiki/Repeating_decimal#Decimal_expansion_and_recurrence_sequence https://en.wikipedia.org/wiki/Repeating_decimal#Decimal_expa... [3] https://softwareengineering.stackexchange.com/a/192081 https://softwareengineering.stackexchange.com/a/192081
- danbruc 9y ago
  This made me look at multiplicative order again and I finally found [1] what I could not find at the time, someone explicitly stating that this is a hard problem. Now it seems so obvious that I should have looked at what cryptography has to say about it that I can not imagine why I did not. Anyway, case finally closed, I got my peace of mind now. [1] https://math.stackexchange.com/questions/837489/algorithms-for-finding-the-multiplicative-order-of-an-element-in-a-group-of-inte https://math.stackexchange.com/questions/837489/algorithms-f...

tadkar 9y ago

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.

danbruc 9y ago
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 <901,532 more digits>« 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 <up to 999,999,991 more digits but maybe also just one>«.
- thaumasiotes 9y ago
  > 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. What's the cycle finding for? Isn't it enough to record the remainder sequence with indices? As soon as any remainder reoccurs, that's the cycle.
  - danbruc 9y ago
    You could of course just maintain the set of remainders seen so far and then you would detect the cycle by reaching a remainder that is already in your set of remainders seen so far but that requires space proportional to the number of digits expanded and if you are expanding a lot of digits and have a large denominator, this will add substantially to the amount of memory consumed. The digits themselves require of course a linear amount of space, too, but only about one byte per digit compared to the potentially big remainder.

siegelzero 9y ago

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.

mrmr1993 9y ago

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 https://en.wikipedia.org/wiki/Repeating_decimal [1]: https://en.wikipedia.org/wiki/Euler%27s_totient_function https://en.wikipedia.org/wiki/Euler%27s_totient_function

danbruc 9y ago
That Wikipedia article on repeating decimals is probably where I started looking into it, but the article is somewhat weird. For many problems Wikipedia articles say we know this and that but those other things are still unknown, this article has a lot of information but does not talk about unknown things at all. The length of the repeating fractional part of 1 / n divides φ(n)...and then nothing. Is this all we know or is there more but just not in this article? 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.
- jcranmer 9y ago
  MathWorld is often a decent resource for finding this kind of information: <http://mathworld.wolfram.com/DecimalPeriod.html> http://mathworld.wolfram.com/DecimalPeriod.html>, but it's often difficult to arrive at those pages if you don't have any idea where to start.
  - yorwba 9y ago
    There's an extra > at the end of your link.

abetusk 9y ago

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 < q. Consider an integer, R, that corresponds to the repeated portion of the rational number (in base 10), with length s (in decimal). This implies: p/q = R sum_{k=1}^{\infty} 10^{-s k} = R / ( 10^s - 1 ) rearranging terms: p (10^s - 1) - q R = 0 Let's just assume for now 10 and q are relatively prime. I think I have to do a little hand waiving at this point and just assume the above has a solution. If the above is true, this means 10^s = 1 (%q) for s equal to the order of 10 mod q, which is a fancy way of saying 10^s = C q + 1 for some integer C. One choice that will always work is taking s = phi(q) though this might be smaller (specifically a divisor or phi(q)) depending on what the order of 10 is to q. 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 And there you go. Assuming that I haven't bungled anything, this also gives an 'algorithm' to find the actual repeated sequence: R = p C = p 10^{phi(q)} . Choosing s, the length of R in base 10, to be phi(q) will always "work", but, again, s might be able to be chosen smaller, depending on what divisors of phi(q) there are and what order 10 is to q, so the real answer of the length of the repeated sequence is 10's order in the multiplicative group mod q. 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 https://softwareengineering.stackexchange.com/a/192077 [2] https://en.wikipedia.org/wiki/Repeating_decimal#Decimal_expansion_and_recurrence_sequence https://en.wikipedia.org/wiki/Repeating_decimal#Decimal_expa... [3] https://softwareengineering.stackexchange.com/a/192081 https://softwareengineering.stackexchange.com/a/192081

danbruc 9y ago
This made me look at multiplicative order again and I finally found [1] what I could not find at the time, someone explicitly stating that this is a hard problem. Now it seems so obvious that I should have looked at what cryptography has to say about it that I can not imagine why I did not. Anyway, case finally closed, I got my peace of mind now. [1] https://math.stackexchange.com/questions/837489/algorithms-for-finding-the-multiplicative-order-of-an-element-in-a-group-of-inte https://math.stackexchange.com/questions/837489/algorithms-f...