[Solved] Arithmetic with base 256 number system

by


So you have power of 2 operations which can be easily converted to bit operations… no bigint lib is needed for such triviality. Let assume you got number

const int n=1000000000; // number size in bytes
BYTE x[n]; // number bytes let num[0] be LSW (least signifficant Word)

So the operations involved are:

  1. mod: y = x%2 = x&1

    this is O(1)

    BYTE y = x[0]&1;

    result is single bit so no need to store it as bigint

  2. div: y = x/2 = x>>1

    this is O(n) and the result is also bigint so

    int i;
BYTE y[n]; // result
BYTE cy; // carry flag
for (cy=0,i=n-1;i>=0;i--) // process all words from MSW to LSW
 {
 y[i] = ((x[i]>>1)&0x7F) | cy; // bitshifted word + last carry
 cy = (x[i]<<7)&0x80; // carry is shifted out lsb of word shifted to msb position
 }

  3. dec: y=x-1

    this is O(n) and the result is also bigint so

    int i;
BYTE y[n]; // result
BYTE cy; // carry flag
for (cy=1,i=0;(i<n)&&(cy);i++) // process all words from LSW to MSW
 {
 y[i] = (x[i]-cy)&0xFF; // y[i] = sbc x[i],0
 cy = (x[i]==0x00); // carry
 }

Hope I did not make some silly syntax error or something as I coded this directly into here…

Both O(n) operations can be done in-place you just need to buffer actual x[i] value or compute carry before x[i] change and buffer old carry

In your case I would use 32bit (DWORD) or 64bit (QWORD) instead of 8bit (BYTE) that will boost the speed as the ALU on most computers is 32 or 64 bit anyway

If you’re interested in implementing more of the bigint stuff see:

  • Cant make value propagate through carry
  • Fast bignum square computation
  • Floating Point Divider Hardware Implementation Details
  • Building a logarithm function in C without using float type
  • Schönhage-Strassen multiplication using NTT

[Edit1] dec for MSW first

int i;
BYTE y[n]; // result
BYTE cy; // carry flag
for (cy=1,i=n-1;(i>=0)&&(cy);i--) // process all words from LSW to MSW
 {
 y[i] = (x[i]-cy)&0xFF; // y[i] = sbc x[i],0
 cy = (x[i]==0x00); // carry
 }

and in-place:

int i;
BYTE cy; // carry flag
for (cy=1,i=n-1;(i>=0)&&(cy);i--) // process all words from LSW to MSW
 {
 x[i] = (x[i]-cy)&0xFF; // y[i] = sbc x[i],0
 if (x[i]==0xFF) cy=1; // carry
 }

3

solved Arithmetic with base 256 number system