num-bigint
num-bigint copied to clipboard
Use divide and conquer in to_radix_digits
This implements the algorithm mentioned in #315
Benchmark:
// prev
running 4 tests
test to_str_radix_10 ... bench: 4,242.41 ns/iter (+/- 712.43)
test to_str_radix_10_2 ... bench: 82,360.73 ns/iter (+/- 13,304.91)
test to_str_radix_10_3 ... bench: 3,929,829.90 ns/iter (+/- 514,647.85)
test to_str_radix_10_4 ... bench: 243,146,081.10 ns/iter (+/- 44,213,689.70)
// now
running 4 tests
test to_str_radix_10 ... bench: 4,261.38 ns/iter (+/- 522.98)
test to_str_radix_10_2 ... bench: 83,358.54 ns/iter (+/- 11,170.02)
test to_str_radix_10_3 ... bench: 2,623,301.20 ns/iter (+/- 279,505.89)
test to_str_radix_10_4 ... bench: 195,073,240.50 ns/iter (+/- 17,025,687.08)
Currently both grow with O(n^2), to make things algorithmically faster we need a faster multiplication and division algorithm.
I would like to implement Burnikel Ziegler for fast division to make to_radix even faster. Would you rather have it in this PR or merge this alone?
I implemented the Burnikel Ziegler, and the result is no longer quadratic:
running 4 tests
test to_str_radix_10 ... bench: 4,447.95 ns/iter (+/- 504.38)
test to_str_radix_10_2 ... bench: 88,899.42 ns/iter (+/- 14,242.49)
test to_str_radix_10_3 ... bench: 1,968,791.90 ns/iter (+/- 231,474.81)
test to_str_radix_10_4 ... bench: 58,370,762.50 ns/iter (+/- 3,103,897.08)
Now the time complexity is O(n^log3). Further improvement needs faster multiplication algorithm.
Sorry I've neglected this -- I will try to review it soon!