factorsOf10.frink

View or download factorsOf10.frink in plain text format


/** This is an attempt to speed up Java's BigDecimal class, specifically the
    createAndStripZerosToMatchScale method.  This method counts the number of
    trailing zeros (in base 10) from a BigInteger.  However, it is potentially
    inefficient when there are a lot of trailing zeroes, because it
    successively divides by 10 many times, which can be very slow.

    This behavior can be seen when dividing, say, 1/3  by 2/3 which will
    return 0.5.   This can be orders of magnitude slower than dividing, say,
    1/7 by 3/7 (which comes out to 0.3333333...)

    The solution here is motivated by a procedure from here:
    http://mathforum.org/library/drmath/view/55908.html
    and some discussion here:
    https://stackoverflow.com/questions/12356442/binary-divisibility-by-10
*/


countPowersOf10[n] :=
{
   powersOfTwo = getLowestSetBit[n]
   if powersOfTwo < 1
      return 0
   
   count = 0
   while n > 0
   {
      lowWord = bitAnd[n, 2^20-1]
      count = count + lowWord
      n = shiftRight[n, 20]
   }

   if (count mod 25) == 0
      
      return min[count, powersOfTwo]
   else
      return 0
}

for n = 1 to 2000
{
   count = countPowersOf10[n]
   if count > 0
      println["$n\tcount:$count"]
}


View or download factorsOf10.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17988 days, 18 hours, 58 minutes ago.