Multiply very big numbers

Projects Programming
1

Hello people,

I want to multiply somehow 32bit and 64bit numbers. I know that arduino uno doesnt support bigger number than 64bit, so Im looking for another way how to do it.

My idea was to store them into arrays and mutiply them but result is really not very accurate :smiley:

So, is there any option for it?

Thank you!!

2
3

I think it depends a bit on what you want to do with it. Do you actually need to store the 96 bit number? Or are you going to divide it again?

And yeah, there are some other implementations :slight_smile:

4

septillion:
I think it depends a bit on what you want to do with it. Do you actually need to store the 96 bit number? Or are you going to divide it again?

And yeah, there are some other implementations :slight_smile:

Well, I need to store him in char array, not in EEPROM, just char array, then I want to send it via wireless module. Module works great so there is not issue, but I need to somehow multiply it and on my receiving site I need to divide it :smiley:

And I dont want to use BigNumber by nick because it takes a lot of space

5

Why do you need to multiply something for transmission and than divide it again???? That does not make sense.

6

its for security purpose :wink: Im using random 32bit and 64bit codes for IDs, cipher etc, and one step is multiply 32 and 64 bit numbers

7

Mm, then you might want to overthink that, especially because you say BigNumber is to big...

8

and what about this:

uint64_t    a_lo = (uint32_t)a;
uint64_t    a_hi = a >> 32;
uint64_t    b_lo = (uint32_t)b;
uint64_t    b_hi = b >> 32;

uint64_t    a_x_b_hi =  a_hi * b_hi;
uint64_t    a_x_b_mid = a_hi * b_lo;
uint64_t    b_x_a_mid = b_hi * a_lo;
uint64_t    a_x_b_lo =  a_lo * b_lo;

uint64_t    carry_bit = ((uint64_t)(uint32_t)a_x_b_mid +
                         (uint64_t)(uint32_t)b_x_a_mid +
                         (a_x_b_lo >> 32) ) >> 32;

uint64_t    multhi = a_x_b_hi +
                     (a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
                     carry_bit;

return multhi;

looks like it could work

9

Of course you can work around it. You could also make an assembly implementation (it's nothing more then extending 16-bit etc) but I doubt it's a very effective uC solution (at least on a 8-bit and/or without hardware multiply...)

10

yep but it doesnt work very well

64bit: 7897673779615492704

b_lo: 2045110880
b_hi: 1838820469

so I dont know how split function works, but this doesnt look like my 64bit number, so all math operations are wrong

11

LadIQe:
its for security purpose :wink: Im using random 32bit and 64bit codes for IDs, cipher etc, and one step is multiply 32 and 64 bit numbers

So this is an xyproblem: you want to implement some sort of security. You imagine multiplication is how
to do this (it isn't - you need encryption or authentication or both perhaps?)

So explain what you are really trying to achieve...

12

as I said, im using random 32bit and random 64bit numbers, than i want to multiply them, use AES encryption, send it, decrypt it on the other side and divide, get IDs and thats all

13

LadIQe:
and what about this:
...
...
looks like it could work

Multiplying two 64 bit numbers and only returning 64 bits will never give you the correct result.

LadIQe:
yep but it doesnt work very well

64bit: 7897673779615492704

b_lo: 2045110880
b_hi: 1838820469

so I dont know how split function works, but this doesnt look like my 64bit number, so all math operations are wrong

Are you printing your numbers as hex?

14

sterretje:
Multiplying two 64 bit numbers and only returning 64 bits will never give you the correct result.
Are you printing your numbers as hex?

hello, no sir, im using this to print 64bit number:

void print(uint64_t value)
{
    const int NUM_DIGITS    = log10(value) + 1;

    char sz[NUM_DIGITS + 1];
    
    sz[NUM_DIGITS] =  0;
    for ( size_t i = NUM_DIGITS; i--; value /= 10)
    {
        sz[i] = '0' + (value % 10);
    }
    
    Serial.print(sz);

}

15 
64bit: 7897673779615492704 = 0x6D9A2C7579E5EA60

b_lo: 0x79E5EA60
b_hi: 0x6D9A2C75

Looks fine to me.