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 17837 days, 7 hours, 28 minutes ago.