[Richard Suchenwirth] 2002-04-27 - Periodic decimal fractions are
numbers where a sequence of digits behind the decimal point (the
''period'') is endlessly repeated, for example:
 1/7 = 0.142857142857..
 1/3 = 0.3333..
The following routine tries to detect a period in a given number and
returns the period (might be 0 for integers or non-strict periods like
 1/2 = 0.5000..
or (implicitly) an empty string if no period could be detected - then
the input number might be irrational (not representable by a
nominator/divisor expression, e.g. sqrt(2)), or it has a period longer
than 7 digits, which can not be confirmed at the maximum
''tcl_precision'' of 17, a limit imposed by the underlying ''double''
representation in C. For instance, 1/17 is certainly periodic, but
the period is out of sight for Tcl's [expr] math..
----
 proc period x {
	set frac [expr {abs(double($x)-int($x))}]
	if {!$frac || [string length $frac]<10} {return 0}
	set digits [string range $frac 2 end]
	foreach n {1 2 3 4 5 6 7} {
	    foreach offset {0 1 2 3 4 5 6} {
    	        set try [string range $digits $offset [expr $offset+$n-1]]
	        if {[regexp .{0,$n}$try\($try)+.{0,$n}$ $digits]} {
		        return $try
                }
	    }
	}
 }
----
[Arjen Markus] As the fraction is contained in a ''string'', there ought to be no problem with very long periods:

   set long_fraction "0.123456789012345678901234567890"

As long, of course, as you avoid interpreting the string as a number!
[RS] admits that he does, by letting [expr] compute the fractional part...
----
[KBK] In the spirit of [Fraction math], let's do the period
of a rational number whose numerator and denominator are integers.
The following has no trouble finding out that 1/17 repeats with a
period of 16 places.  It also handles Arjen's problem nicely, if
we remember that .12345678901234567890... = 137174210/1111111111

 proc period2 { n d } {
     set x 0
     while { 1 } {
         set r [expr { $n % $d }]
         if { $r == 0 } {
             return 0
         } elseif { [info exists seen($n)] } {
             return [expr { $x - $seen($n) }]
         } else {
             set seen($n) $x
             incr x
             set n [expr { 10 * $r }]
         }
     }
 }
 for { set i 1 } { $i <= 20 } { incr i } {
     puts [list $i [period2 1 $i]]
 }

There is some interesting number theory here, but I haven't the time to
get into it; I've typed this in in about 15 minutes while waiting for
a test to run.
----
[Arjen Markus] Independently of Kevin, I came up with the following proc that will return the decimal string/number of such a division with any precision you like (also known as ''long division'', if I have translated this correctly):

   # decimalFraction --
   #    Determine the decimal fraction of num/denom by a given precision
   #
   # Arguments:
   #    num      Numerator of the fraction
   #    denom    Denominator of the fraction
   #    nodec    Number of decimals required
   # Result:
   #    The decimal fraction (as a string!)
   # Notes:
   #    The method relies entirely on integer division and can achieve
   #    any precision required.
   #
   proc decimalFraction { num denom nodec } {
      #
      # The integer part first
      #
      set fract  [expr {int($num/$denom)}]
      set rem    [expr {$num%$denom}]
      set result "$fract"
      append result "."

      #
      # Loop over the decimals
      #
      for { set i 0 } { $i < $nodec } { incr i } {
         set rem [expr {$rem*10}]
         if { $rem < $denom } {
            append result "0"
         } else {
            set fract [expr {int($rem/$denom)}]
            set rem   [expr {$rem%$denom}]
            append result "$fract"
         }
      }

      return $result
   }

   #
   # A few test cases
   #

   puts [decimalFraction 1 3 10]
   puts [decimalFraction 1 5 10]
   puts [decimalFraction 1 13 40]
   puts [decimalFraction 1 97 200]
   puts [decimalFraction 1 15 10]
   puts [decimalFraction 1 17 40]
   puts [decimalFraction 1 7 40]

The number-theoretical aspects of this problem relate (probably among other things, but I am only an amateur :-) to Fermat's little theorem:

   a^(p-1)-1 is divisible by p, 

if p is a prime and a is not a multiple of p.

This allows us to put an upper limit to the period of any prime, say 127, which is one of my favourites: the period for 127 can not be more than 126, and otherwise it will be a factor of 126). The latter follows from the observation that:

   a^gh-1 = m^h-1 = (m-1)*(1+m+m^2+...m^h) (where m=a^g)

----
[Category Mathematics] | [Arts and crafts of Tcl-Tk programming]