math.big.div will hang when the number beyond some value

[kbkpbot]

Describe the bug

When use big number div, it will hang when the number beyond some value.

Reproduction Steps

big.v

module main

import math.big
import strconv
import os

const d_2 = big.integer_from_int(2)
const d_4 = big.integer_from_int(4)
const d_10 = big.integer_from_int(10)

fn main() {
	mut n := 96320
	if os.args.len > 1 {
		n = strconv.atoi(os.args[1]) or { n }
	}

	dump(n)
	base := d_10.pow(u32(n - 1))
	a := d_4*base    // 40000000....00
	b := d_2*base   //  20000000....00
	dump(a.bit_len())
	dump(b.bit_len())
	c := a / b          // c should be 2
	dump(c.bit_len())
	dump(c)
}

  v big.v -prod
 ./big 96320
./big 96321

Expected Behavior

mars@mars-QiTianM428-A688:~/v/bug$ ./big
[big.v:17] n: 96320
[big.v:21] a.bit_len(): 319967
[big.v:22] b.bit_len(): 319966
[big.v:24] c.bit_len(): 2
[big.v:25] c: 2

mars@mars-QiTianM428-A688:~/v/bug$ ./big 96321
[big.v:17] n: 96321
[big.v:21] a.bit_len(): 319971
[big.v:22] b.bit_len(): 319970
[big.v:24] c.bit_len(): 2
[big.v:25] c: 2

Current Behavior

mars@mars-QiTianM428-A688:~/v/bug$ ./big
[big.v:17] n: 96320
[big.v:21] a.bit_len(): 319967
[big.v:22] b.bit_len(): 319966
[big.v:24] c.bit_len(): 2
[big.v:25] c: 2

mars@mars-QiTianM428-A688:~/v/bug$ ./big 96321
[big.v:17] n: 96321
[big.v:21] a.bit_len(): 319971
[big.v:22] b.bit_len(): 319970

the second run will hang ....

Possible Solution

No response

Additional Information/Context

No response

V version

V 0.4.9 ab2eb00

Environment details (OS name and version, etc.)

V full version	V 0.4.9 ab2eb00
OS	linux, Ubuntu 24.04.2 LTS
Processor	8 cpus, 64bit, little endian, Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
Memory	13.86GB/15.51GB
V executable	/media/HD/github/kbkpbot/v/v
V last modified time	2025-02-25 14:20:44
V home dir	OK, value: /media/HD/github/kbkpbot/v
VMODULES	OK, value: /home/mars/.vmodules
VTMP	OK, value: /tmp/v_1000
Current working dir	OK, value: /home/mars/v/bug
Git version	git version 2.43.0
V git status	weekly.2025.09-1-gab2eb001
.git/config present	true
cc version	cc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
gcc version	gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
clang version	Ubuntu clang version 18.1.3 (1ubuntu1)
tcc version	tcc version 0.9.28rc 2024-07-31 HEAD@1cee0908 (x86_64 Linux)
tcc git status	thirdparty-linux-amd64 0134e9b9-dirty
emcc version	N/A
glibc version	ldd (Ubuntu GLIBC 2.39-0ubuntu8.4) 2.39

Note

You can use the 👍 reaction to increase the issue's priority for developers.

Please note that only the 👍 reaction to the issue itself counts as a vote.
Other reactions and those to comments will not be taken into account.

[huly-for-github]

Connected to Huly®: V_0.6-22216

[spytheman]

It depends on const newton_division_limit = 10_000 in vlib/math/big/array_ops.v .

If I change it to const newton_division_limit = 100_000, the program runs fine.

That constant is used in only one place, like this:

const newton_division_limit = 100_000

@[inline]
fn divide_array_by_array(operand_a []u32, operand_b []u32, mut quotient []u32, mut remainder []u32) {
    if operand_a.len >= newton_division_limit {
        newton_divide_array_by_array(operand_a, operand_b, mut quotient, mut remainder)
    } else {
        binary_divide_array_by_array(operand_a, operand_b, mut quotient, mut remainder)
    }
}

i.e. if the first operand length is bigger than the constant, it forces the calculation to use newton_divide_array_by_array, and presumably the bug is there.

If not, it uses the simpler binary_divide_array_by_array, which does not exhibit the bug.

96321 is just the first n, for which a.len becomes 10000 .

[spytheman]

newton_divide_array_by_array was added in #11487 , with a comment:

The limit has been set high because these algorithm, although more efficient, are slower because of the numerous allocations on the heap.
Nevertheless for very large numbers these algorithm can be more efficient.

[spytheman]

I tested with bumping the constant to const newton_division_limit = 1_000_000, and I got a result in a reasonable time for even n=993000:

#0 04:35:59 ^ master ~/code/v>v -cc clang-18 -keepc -cg x.v
#0 04:36:02 ^ master ~/code/v>time ./x 993000
[x.v:17] n: 993000
[x.v:21] a.bit_len(): 3298674
[x.v:22] b.bit_len(): 3298673
[/home/delian/code/v/vlib/math/big/array_ops.v:252] operand_a.len: 103084
[x.v:24] c.bit_len(): 2
[x.v:25] c: 2

real	0m2.298s
user	0m2.288s
sys	0m0.010s
#0 04:36:09 ^ master ~/code/v>

[spytheman]

newton_divide_array_by_array gets stuck in this loop:

    for lastx != x { // main loop
        lastx = x
        x = (x * (pow2_k_plus_1 - (x * b))).right_shift(u32(k))
    }

The values for x get divergent (and growing) for some reason for bigger k values, where k is defined as k := a.bit_len() + b.bit_len() // a*b < 2**k .

[spytheman]

Given the divergent loop, perhaps we should just not use newton_divide_array_by_array at all, for any sizes, until the underlying bug is found.

I also saw empirically, that binary_divide_array_by_array is a lot more performant for the operand_a.len < 10_000 and it seems to scale better with growing length.

I have not done extensive analysis, but given both the performance and correctness drawbacks of newton_divide_array_by_array, I do not see why it should exist/be used at all.

[spytheman]

@VincentLaisney , @hungrybluedev what do you think?

[spytheman]

I've added vlib/math/big/big_division_test.v in latest V in 9b8a160, for easier testing and to prevent silent regressions.

[hungrybluedev]

I'm happy to keep binary division and drop newton division.

[kbkpbot]

It maybe related to multiplication toom3_multiply_digit_array or karatsuba_multiply_digit_array.
And also the newton division need some optimization.