util: Implement modulo for arith_uint256 #16357

pull nkostoulas wants to merge 1 commits into bitcoin:master from nkostoulas:uint256-modulo changing 3 files +39 −0

nkostoulas commented at 11:50 PM on July 8, 2019: contributor

I've implemented this for some side work and thought it might be of interest.
Implement modulo for arith_uint256 92d3dd973c
nkostoulas renamed this:
~~Implement modulo for arith_uint256~~
util: Implement modulo for arith_uint256
on Jul 8, 2019

in src/arith_uint256.cpp:117 in 92d3dd973c

 112 | +{
 113 | +    base_uint<BITS> div = b;     // make a copy, so we can shift.
 114 | +    base_uint<BITS> num = *this; // make a copy, so we can subtract.
 115 | +    int num_bits = num.bits();
 116 | +    int div_bits = div.bits();
 117 | +    if (div_bits == 0)

qmma70 commented at 12:38 AM on July 9, 2019:

Could probably throw before making the copies?

in src/arith_uint256.cpp:128 in 92d3dd973c

 123 | +    while (shift >= 0) {
 124 | +        if (num >= div) {
 125 | +            num -= div;
 126 | +        }
 127 | +        div >>= 1; // shift back.
 128 | +        shift--;

qmma70 commented at 12:39 AM on July 9, 2019:

Minor: --shift; would be a better.

qmma70 commented at 12:47 AM on July 9, 2019: contributor

How is this going to be used?
sipa commented at 12:48 AM on July 9, 2019: member

What is this useful for? AFAIK we don't use or need moduli with big numbers anywhere.
laanwj commented at 8:07 AM on July 9, 2019: member

Thanks for your contribution.

However, if there's no use case of this within bitcoin, it doesn't make sense for it to be merged here. arith_uint256 exists for some specific uses in our code and is by no means a general bignum implementation. It's also not exported as a library for others.
laanwj closed this on Jul 9, 2019
MarcoFalke locked this on Dec 16, 2021

Contributors