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