{"id":5726,"date":"2022-08-30T06:46:49","date_gmt":"2022-08-30T01:16:49","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-arithmetic-with-base-256-number-system\/"},"modified":"2022-08-30T06:46:49","modified_gmt":"2022-08-30T01:16:49","slug":"solved-arithmetic-with-base-256-number-system","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-arithmetic-with-base-256-number-system\/","title":{"rendered":"[Solved] Arithmetic with base 256 number system"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

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<\/p>\n

const int n=1000000000; \/\/ number size in bytes\nBYTE x[n]; \/\/ number bytes let num[0] be LSW (least signifficant Word)\n<\/code><\/pre>\n
So the operations involved are:<\/p>\n
    \n
  1. \n
    mod: y = x%2 = x&1<\/code><\/strong><\/p>\n
    this is O(1)<\/code><\/p>\n
    BYTE y = x[0]&1;\n<\/code><\/pre>\n
    result is single bit so no need to store it as bigint<\/p>\n<\/li>\n
  2. \n
    div: y = x\/2 = x>>1<\/code><\/strong><\/p>\n
    this is O(n)<\/code> and the result is also bigint so<\/p>\n
    int i;\nBYTE y[n]; \/\/ result\nBYTE cy; \/\/ carry flag\nfor (cy=0,i=n-1;i>=0;i--) \/\/ process all words from MSW to LSW\n {\n y[i] = ((x[i]>>1)&0x7F) | cy; \/\/ bitshifted word + last carry\n cy = (x[i]<<7)&0x80; \/\/ carry is shifted out lsb of word shifted to msb position\n }\n<\/code><\/pre>\n<\/li>\n
  3. \n
    dec: y=x-1<\/code><\/strong><\/p>\n
    this is O(n)<\/code> and the result is also bigint so<\/p>\n
    int i;\nBYTE y[n]; \/\/ result\nBYTE cy; \/\/ carry flag\nfor (cy=1,i=0;(i<n)&&(cy);i++) \/\/ process all words from LSW to MSW\n {\n y[i] = (x[i]-cy)&0xFF; \/\/ y[i] = sbc x[i],0\n cy = (x[i]==0x00); \/\/ carry\n }\n<\/code><\/pre>\n<\/li>\n<\/ol>\n
    Hope I did not make some silly syntax error or something as I coded this directly into here…<\/p>\n
    Both O(n)<\/code> operations can be done in-place you just need to buffer actual x[i]<\/code> value or compute carry before x[i]<\/code> change and buffer old carry <\/p>\n
    In your case I would use 32bit (DWORD) or 64bit (QWORD) instead of 8bit (BYTE) that will boost the speed as the ALU<\/strong> on most computers is 32<\/code> or 64<\/code> bit anyway<\/p>\n
    If you’re interested in implementing more of the bigint stuff see:<\/p>\n