/** This is an new timing test to see how well Frink's updated routines parse large integers more rapidly than Java currently does with its BigInteger(String) constructor, which is O(n^2) in the number of digits. 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 currently 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 = parseInt[str] // Frink native call end = now[] return end-start } // Timing test lastTime = undef for k = 1 to 2 for i=1 to 7 { n = 10^(10^i) - 1 str = toString[n] iterations = 10^max[7-i, 0] time = parseRecursiveTime[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 }