Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

subtracting binaries

 [1/10] from: maarten:vrijheid at: 1-Apr-2004 16:55


Hi, As anybody (efficiently) tackled suntracting two binary! values. I want to compute the difference between two 160 bit SHA1 keys, with the outcome a new binary. And I also need addition which sould be circular in 160bit space. E.g 2^160 + 1 = 1 Before re-inventing yet another wheel I'd thought I'd ask to see if anybody has already written this. --Maarten

 [2/10] from: antonr:lexicon at: 2-Apr-2004 3:16


I was helping Oldes with the problem of computing a long checksum a while back. The code I came up with is at the bottom. It can give you some ideas maybe. Anton.
> Hi, > As anybody (efficiently) tackled suntracting two binary! values. I want
<<quoted lines omitted: 4>>
> anybody has already written this. > --Maarten
; can use pairs to store integers better and wrap around automatically ; without math overflow error! :) (Romano's tip) sum: 2147483647 add-val: func [val][ sum: either error? try [sum + val][ ; which way did it overflow? (positive/negative) either positive? sum [ print "positive" ; overflowed in positive direction ; to-integer required because -2147483648 is by default a decimal ;print ["(sum + to-integer -2147483648):" (sum + to-integer -2147483648) type? (sum + to-integer -2147483648)] ;print ["(val + to-integer -2147483648):" (val + to-integer -2147483648) type? (val + to-integer -2147483648)] (sum + to-integer -2147483648) + (val + to-integer -2147483648) ][ print "negative" ; overflowed in negative direction (2147483647 + sum) + (2147483647 + val) + 2 ] ][sum + val] ; no error, just add it up probe type? sum sum ]

 [3/10] from: maarten::vrijheid::net at: 1-Apr-2004 19:56


Neat idea, but with 2^161 module 2^160 I have a problem. I'll see if I can do something with series. --Maarten Anton Rolls wrote:

 [4/10] from: tomc:darkwing:uoregon at: 1-Apr-2004 13:33


Hi Maarten, I had played with big number math a few years back some of it might be useful. I have no idea where it is as far efficiency is concerned. http://uoregon.edu/~tomc/b24b.r basicly parts for a base 24bit math lib, I only took it far enough to do some basic proof of concepts and is glaringly missing decimal <-> b24 translations but I expect in your case as well the actual decimal values are irrelavent. On Thu, 1 Apr 2004, Maarten Koopmans wrote:

 [5/10] from: mauro:fontana:speedautomazione:it at: 2-Apr-2004 10:16


On Thu, 01 Apr 2004 16:55:27 +0200, Maarten Koopmans <[maarten--vrijheid--net]> wrote:
> Hi, > As anybody (efficiently) tackled suntracting two binary! values. I want
<<quoted lines omitted: 3>>
> Before re-inventing yet another wheel I'd thought I'd ask to see if > anybody has already written this.
If you are trying to build a Galois Field the best way is probably building an array with the exponential form so that you can do math on exponents only (you do the modulus on the exponent). M&F

 [6/10] from: greggirwin:mindspring at: 2-Apr-2004 16:43


Hi Maarten, I know I have other things to be doing :), but this kept coming up in my mind...wondering if doing binary math on bitsets would work. The following is very much a proof-of-concept, but it might be an idea worth pursuing. -- Gregg ---------------------------------------------------------------- get-bit: func [bitset index "0 to n-1"] [either find bitset index [1][0]] set-bit: func [bitset index "0 to n-1"] [insert bitset index] bit-set?: func [bitset index "0 to n-1"] [found? find bitset index] clear-bit: func [bitset index "0 to n-1"] [remove/part bitset index] add-bitsets: func [a b /local c i n carry] [ carry: 0 c: make bitset! length? a for i 0 (length? a) - 1 1 [ n: add get-bit a i get-bit b i ;print [get-bit a i get-bit b i n] switch n + carry [ 0 [] 1 [set-bit c i carry: 0] 2 [carry: 1] 3 [set-bit c i carry: 1] ] ;repeat i length? c [prin form get-bit c i - 1] print [tab carry] ] i: 0 if carry <> 0 [ while [bit-set? c i][ clear-bit c i i: i + 1 ] set-bit c i ] c ] subtract-bitsets: func [a b] [ if a = b [return make bitset! length? a] add-bitsets a complement b ] mb: func [val][make bitset! val] add-bitsets mb #{00} mb #{00} add-bitsets mb #{01} mb #{02} add-bitsets mb #{F0} mb #{0F} add-bitsets mb #{FF} mb #{FF} add-bitsets mb #{FF} mb #{01} subtract-bitsets mb #{00} mb #{00} subtract-bitsets mb #{02} mb #{01} subtract-bitsets mb #{FF} mb #{0F} subtract-bitsets mb #{FF} mb #{FF} subtract-bitsets mb #{00} mb #{01} subtract-bitsets mb #{00} mb #{FF}

 [7/10] from: maarten:vrijheid at: 3-Apr-2004 8:14


Hi Gregg,
> I know I have other things to be doing :), but this kept coming up in my > mind...wondering if doing binary math on bitsets would work.
I considered series! (or actually, block!). Bitset! is interesting as well. What did I do so far: result: copy [] parse enbase/base checksum/secure mold now/precise 2 [ any [ "1" (append result 1) | "0" (append result 0)]] This makes for easy computation with a for loop counting backwards (or doing it big-endian and going forward after reversing). As my problem only needs to initialize once the parse is OK. Now, back to a binary is also easy: debase/base rejoin result 16 Funny: > < and maximum-of and minimum-of work on binaries! So comparison is easy (it's also an important part of what I need).
> The following is very much a proof-of-concept, but it might be an idea > worth pursuing. >
Thanks! Now.... why do I want to do all this? --Maarten

 [8/10] from: maarten:vrijheid at: 3-Apr-2004 9:32


Hi Gregg , I tested it some more, and it works like a charm! Thanks for the time-saver. Especially the fact that it works modulo (max value of the supplied binary) is really nice. And getting it back to a binary is simple:
>> a: add-bitsets mb checksum/secure mold now mb checksum/secure mold
now/precise == make bitset! #{A2B6BECF9C1DC2F6C8F35FAD01DD46BF6545EDB4}
>> make binary! a
== #{ A2B6BECF9C1DC2F6C8F35FAD01DD46BF6545EDB4000000000000000000000000 }
>> copy/part make binary! a 20
== #{A2B6BECF9C1DC2F6C8F35FAD01DD46BF6545EDB4} BTW: I never really "got" bitsets (shame) so if anybody wants to elaborate on how the various operation on bitsets work... The docs don't mention the bitset! value at all, except for parse (where I used it). Thanks! --Maarten Gregg Irwin wrote:

 [9/10] from: greggirwin:mindspring at: 3-Apr-2004 10:33


Hi Maarten, MK> I tested it some more, and it works like a charm! Thanks for the MK> time-saver. Especially the fact that it works modulo (max value of the MK> supplied binary) is really nice. Great! I wasn't sure if I had overlooked something, or if it was what you wanted. I won't spend time on it now, but eliminating FOR is an obvious speed trap (~30%): add-bitsets: func [a b /local c i n carry] [ carry: 0 c: make bitset! length? a repeat i (length? a) - 1 [ n: i - 1 switch carry + add get-bit a n get-bit b n [ 0 [] 1 [set-bit c n carry: 0] 2 [carry: 1] 3 [set-bit c n carry: 1] ] ] if carry <> 0 [ i: 0 while [bit-set? c i][ clear-bit c i i: i + 1 ] set-bit c i ] c ] MK> BTW: I never really "got" bitsets (shame) so if anybody wants to MK> elaborate on how the various operation on bitsets work... The docs don't MK> mention the bitset! value at all, except for parse (where I used it). I just derived my stuff via experimentation. Occasionally I look at old libraries I've done and port pieces of them. I had an old bit-vector class I pseudo-ported (haven't done bit-matrix yet :) and just played around to see how they worked. Things like UNION, DIFFERENCE, and INTERSECT also work on them, which is nice. Now, if only we had native SHIFT and ROTATE functions... -- Gregg

 [10/10] from: greggirwin:mindspring at: 5-Apr-2004 16:59


Oops! Small glitch in the optimized version (missed a bit). Fixed: add-bitsets: func [a b /local c i n carry] [ carry: 0 c: make bitset! length? a repeat i (length? a) [ n: i - 1 switch carry + add get-bit a n get-bit b n [ 0 [] 1 [set-bit c n carry: 0] 2 [carry: 1] 3 [set-bit c n carry: 1] ] ] if carry <> 0 [ i: 0 while [bit-set? c i][ clear-bit c i i: i + 1 ] set-bit c i ] c ] -- Gregg

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted