/** This is an attempt to parse large integers more rapidly than Java currently
    does with its BigInteger(String) constructor, which is O(n^2) in the
    number of digits.

    NOTE:  As of the 2017-04-12 release of Frink, this recursive parsing is
    done automatically when Frink parses integers, and this file is no longer
    necessary.  The performance improvement was striking.  For example,
    parsing the largest-known Mersenne prime 2^74207281-1 went from 13124
    seconds (that's about 218 minutes) down to 68.392 s (just over a minute),
    a factor of 192 times faster!  This improvement makes parsing of giant
    numbers from Java's worse-than O(n^2) to about O(n^1.513) at 10 million
    digits (with a good constant.)

    See:
    https://stackoverflow.com/questions/14757086/new-bigintegerstring-performance-complexity?rq=1

    This algorithm is a recursive divide-and-conquer algorithm that is
    extremely simple.  It recursively the string into two approximate halves
    (the halves don't have to be exact,) and calls itself on each half of the
    result.  The result is calculated as:

    parseRecursive[left] * radix^length[right] + parseRecursive[right]

    NOTE:  This version only handles positive numbers.
*/
parseRecursive[str] :=
{
   len = length[str]

   if len <= 1280             // TODO:  Tune this threshold
      return parseInt[str]   // Bottom case, use non-recursive built-in routine
   
   halfLen = len div 2
   left =   left[str, -halfLen]  // Whatever's left after taking halfLen chars
                                 // from the right
   right = right[str,  halfLen]  // Take exactly halfLen chars from the right

   return parseRecursive[left] * 10^halfLen + parseRecursive[right]
}


// Parse recursively and test the result.  This returns the time taken
// by the parseRecursive call.  It does not include the (possibly much greater)
// time taken by the old parseInt[str] call that it's testing against.
parseRecursiveTest[str, iterations=1] :=
{
   start = now[]
   result = -1
   for i = 1 to iterations
      result = parseRecursive[str]
   end = now[]
   if result != parseInt[str]
      println["Error:\n in:  $str\n out: $result"]
   return end-start
}

// Parse recursively and time the result, returning the time taken.
parseRecursiveTime[str, iterations] :=
{
   start = now[]
   for i = 1 to iterations
      result = parseRecursive[str]
   end = now[]
   return end-start
}

// Timing test
lastTime = undef

for i=1 to 7
{
   n = 10^(10^i) - 1
   str = toString[n]

   iterations = 10^max[7-i, 0]
   time = parseRecursiveTest[str, iterations]
   
   print["Time to parse " + length[str] + " digits ($iterations iterations):\t" + format[time, "ms", 0]]
   
   if lastTime != undef  && lastTime > 0 s && time > 0 s
   {
      time = time/iterations
      order = log[time/lastTime] / log[10]
      println["\tO(n^" + format[order, 1, 3] + ")"]
   } else
      println[]

   lastTime = time
}