in reply to Re^5: Introspection into floats/NV
in thread Introspection into floats/NV

I think there is a generic formula to calculate these using prime factors.

But I get your point, seeing the periodic portion in hex would be different.

While the period's length might be the same, the discrepant becomes only one quarter of what it was.

Cheers Rolf
(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery

Replies are listed 'Best First'.
Re^7: Introspection into floats/NV (math behind periodic numbers)
by LanX (Saint) on Jun 05, 2025 at 15:13 UTC
    > I think there is a generic formula to calculate these using prime factors.

    I looked into it, there is a trivial and less trivial part to it.

    (I'm writing it down for therapeutically reasons, because wanna stop reinvent Euler's wheels again)

    for shortened p/q* and with q* =  q * 2^i for i in N0, and p,q in N.

    (i.a.W. ignore prime factors of 2)

    The period is the smallest k for which there is a factor l such that q*l= 2^k -1 (aka ord2(q) said order of 2 modulo q)

    The periodic fraction will be p*l , because 1/ 2^k-1 is a periodic fraction of the length k and sequence '0...01'. (that's similar to 1/9, 1/99, ... in decimal, same math, we did this in school)

    Example 1/5 = 3/15 =  3/2**4-1 = 0.[0011] because 1/15 = 0.0001

    DB<15> $, =","; say unpack "A1A11A*",unpack "B*", pack "F>", 1/5 0,01111111100,1001100110011001100110011001100110011001100110011010 DB<16> $, =","; say unpack "A1A11A*",unpack "B*", pack "F>", 1/15 0,01111111011,0001000100010001000100010001000100010001000100010001

    NB: The exponents are different to normalize the mantissa.

    That was the trivial part. ;-)

    The rest dives into number theory

    for a concrete formula° to deduce k from q one needs q's prime factors and Eulers phi function (it eludes me why this is called Totient in English)

    for many - not all - prime numbers q holds k = q-1 (e.g 3, 5, but not 7)

    In the case of 1/121 (NB 121=11**2) we have a period of 110 = 10 ** 11 digits, easily cracking the 53 bits of a double float.

    This is also exemplifies why rational numbers can't be fixed by adding the period length to floats, storing 1 and 121 is far more precise. OTOH floats are capable of approximating many non-rational numbers like pi.

    DISCLAIMER: not a mathematical text, I wrote it down as fast as possible, here are typos, dragons and typodragons. ;-)

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    see Wikisyntax for the Monastery

    °) There are detailed Math Exchange on the topic see https://math.stackexchange.com/questions/1025578/is-there-a-better-way-of-finding-the-order-of-a-number-modulo-n#1025593

    Update

    here a brutal but O(n) efficient way to calculate it even for very long periods:

    sub period_length { my $q = shift ; until ( $q % 2 ) { $q /= 2 }; my $r=1; # say "q:$q"; for (1..$q) { $r = $r * 2 % $q; return $_ if $r == 1; # say "r:$r" } }