-
-
Notifications
You must be signed in to change notification settings - Fork 925
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Improve Bignum string parsing #1258
Comments
Taking a look at this now. This is my first foray into JRuby, so anybody who wants to leapfrog me, feel free. :-) |
This is a ruby implemetation. require 'benchmark'
def to_fixnum str
str.to_i
end
$max_digit_fixnum = 18
def to_bignum str
size = str.size
return to_fixnum(str) if size <= 18
# str to array base 10**$max_digit_fixnum least significant digit first
digits = []
j = size - 1
i = j - $max_digit_fixnum + 1
while j >= 0
s = str[i..j]
digits << to_fixnum(s)
j = i-1;
i = j - $max_digit_fixnum + 1
i = 0 if i < 0
end
# reduce digits from base b10x to b10x*b10x
n = digits.size
b10x = 10**$max_digit_fixnum
while n > 1
i = 0; j = 0
while i < n.div(2)
digits[i] = digits[j] + digits[j+1]*b10x
i += 1; j += 2
end
if (j == n-1)
digits[i] = digits[j]
i += 1
end
n = i
b10x = b10x*b10x
end
digits[0]
end
# to_bignum without method str.to_i
def to_bignum2 str
size = str.size
i = size - 1
digits = []
while i > 0
digits << (str[i].ord + 10*(str[i-1].ord) - 11 *('0'.ord))
i -= 2;
end
digits << (str[i].ord - '0'.ord) if i == 0
n = digits.size
p10 = 10*10
while n > 1
i = 0; j = 0
while i < n.div(2)
digits[i] = digits[j] + digits[j+1]*p10
i += 1; j += 2
end
if (j == n-1)
digits[i] = digits[j]
i += 1
end
n = i
p10 = p10*p10
end
digits[0]
end
puts Benchmark.realtime {10000.times {to_bignum("1"*100)}}
puts Benchmark.realtime {10000.times {to_bignum2("1"*100)}}
puts
x_my = 0
x = 0
str = "1" * 1000*1000
puts Benchmark.realtime { x_my = to_bignum(str)}
puts Benchmark.realtime { x = (str).to_i }
puts Benchmark.realtime { x_my = to_bignum2(str)}
puts Benchmark.realtime { x = (str).to_i }
puts
puts x_my.size
puts (x_my - x) |
@headius Not yet. I've been fettered by my newness to the ecosystem (e.g. not knowing what tools are available to debug or inspect what's going on). I'm hoping to look at this again this weekend, but again, if anybody wants to leapfrog me on this, feel free. I'm not going to come back and say "hey! I was working on that!" :-) |
Hedius, i tryed three different algorithms
All three are more efficent with a large group(512) of decimal digit converted with #to_i. On MRI 2.0 the best (10X) is algorithm 3. This puzzles me! On JRuby algorithm 1 is the best. The code
|
This was fixed by #3211 above. We are still slower than MRI but many times faster than we were (on both 1.7.x and 9.x). Perhaps we can improve further but this is good enough to declare victory for today. |
JRuby currently uses Java's BigInteger to handle String#to_i when it might need a Bignum. However, this algorithm is quite a bit slower than the one in MRI 2.1.
I had a quick look at the algorithm and I don't think it would be hard to mimic.
The text was updated successfully, but these errors were encountered: