Download or view RecursiveParseStringNative.frink in plain text format
/** 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
}
Download or view RecursiveParseStringNative.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 19967 days, 0 hours, 45 minutes ago.