search

nim-lang / bigints

BigInts for Nim
MIT License
123 stars 32 forks source link

Karatsuba multiplication #95

Open dlesnoff opened 2 years ago

dlesnoff commented 2 years ago

This is still a draft. I get a strange error in one test of the tliterals.nim file. I have no clue why this test is wrong when I switch the karatsuba multiplication.

dlesnoff commented 2 years ago

Lack tests for multiplication.

dlesnoff commented 1 year ago

Thanks. I am not sure I can continue working on this PR, I am terribly busy. I will try to move away the tests under the when isMainModule instruction block. Maybe I will test your suggestion, but I do not think I will have time to do much debugging.

Furthermore, I am really concern by the choice of uint32 vs uint64 (as suggested by @mratsim). This seems to be a big change for the library, that we need to tackle beforehand.

konsumlamm commented 1 year ago

Furthermore, I am really concern by the choice of uint32 vs uint64 (as suggested by @mratsim). This seems to be a big change for the library, that we need to tackle beforehand.

Changing that requires proper support for addition and multiplication of uint64 without overflow (and I don't think writing that in assembly is a good solution). I don't see what that has to do with Karatsuba multiplication though, it doesn't really change the algorithm.