num-bigint icon indicating copy to clipboard operation
num-bigint copied to clipboard

Use divide and conquer in to_radix_digits

Open HKalbasi opened this issue 1 year ago • 3 comments

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.

HKalbasi avatar Dec 16 '24 19:12 HKalbasi

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?

HKalbasi avatar Dec 18 '24 13:12 HKalbasi

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.

HKalbasi avatar Jan 02 '25 11:01 HKalbasi

Sorry I've neglected this -- I will try to review it soon!

cuviper avatar Mar 05 '25 19:03 cuviper