Multiplication Algorithms

[Kronuz]

What multiplication algorithm are you using here for uint128_t and uint256_t? I don’t see this algorithm in your integer repository... why?

[armchaircaver]

Surely Jason's code implements this via the operator overload starting in line 208 of uint128_t.cpp :
uint128_t uint128_t::operator*(const uint128_t & rhs) const{
...

By the way, you may be interested in the modified version of this operator overload that I wrote to solve a contest center puzzle, described in http://arthurvause.blogspot.co.uk/2017/05/three-pandigitals.html

[calccrypto]

I do long multiplication in uint128_t and uint256_t because these two types have fixed numbers of internal digits, and thus multiplication can be done in constant time. I have implemented long multiplication in integer, but it is relatively slow, when compared to other algorithms, which is why I have a list of commented out multiplication methods that are implemented but not used.

[Kronuz]

For modulo and divisions, have you tried Barrett? There’s also other method which combines Newton Inversion with Barrett’s algorithm (Newton Division), there’s an interesting paper here comparing algorithms: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.9736&rep=rep1&type=pdf

[calccrypto]

Cool! Thanks! I'll get to it at some point.

[Kronuz]

I made a ton of additions/changes in https://github.com/Kronuz/uint_t lots of optimizations and quite a few algorithms

[calccrypto]

Nice!