What overflow problem I thought when I came up with
add32 =: 65521&|@:
+ NB. add modulo 65521
a32mdslow =: ((1 add32{:)(+ 16 (33 b.)])
(#add32(add32/)))@:(add32/\)@(a.&i.)
and then I tested it on modest
size input and found it was ORDERS
of magnitude slower than Bill's
loopy version!
So this version guarantees no overflow but at huge
cost.
Deferring taking residues results in:
a32md =: ((1 add32 {:)
(+ ((16) 33 b. ])) 65521 | +/@:>:)@:(+/\)@(a.&i.)
which is somewhat
faster (~3x) but also fatter (~2x) than Raul's,
which is itself
considerably faster than Bill's for a megabyte of data.
Both (a32md
and Raul's a32) appear to produce the same results
as Bill's
presumably correct function for arguments up to 1e7 in length.
I
continue to be puzzled by the poor performance of something
like
add32/\ compared to +/\ .
Performance doesn't change with add32 =:
65521&|@+
Mike
On 24/08/2014 09:37, Raul Miller wrote:
> I believe
this is equivalent, and a bit faster:
>
> a32=: 65536#. 65521| _1 0+ [:
(+/ , {.) 65521| [:+/\. 1,~ a.i. |.
>
> a32 'Wikipedia'
> 300286872
> a32 'The quick brown fox jumps over the lazy dog'
> 1541148634
>
>
Thanks,
>
Raul
On Sun, Aug 24, 2014 at 4:05 AM, bill lam <bbill.
[email protected]> wrote:
> Does anyone have a J-ish solution to adler32
checksum
> and avoid overflow to floating points ?
>
> Adler-32 is
composed of two sums accumulated per byte: s1 is
> the sum of all
bytes, s2 is the sum of all s1 values. Both sums
> are done modulo
65521. s1 is initialized to 1, s2 to zero. The
> Adler-32 checksum is
stored as s2*65536 + s1 in most-
> significant-byte first (network)
order.
>
> * https://www.ietf.org/rfc/rfc1950.txt> *
> http://en.wikipedia.org/wiki/Adler-32
>
> direct translation to J
>
> adler32=: 3 : 0
> 's1 s2'=. 1 0
>
for_a. a.i.y do.
> s1=. 65521 | s1 + a
> s2=. 65521 | s2 + s1
>
end.
> s1 + 16 (33 b.) s2
> )
>
> test data:
>
> adler32 'Wikipedia'
>
300286872
>
> adler32 'The quick brown fox jumps over the lazy dog'
>
1541148634
>
> --
> regards,
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
