an approach that should be fast and also allows resuming where you left off,
and avoiding many |
([: ({: , [: <: +/) +/\) 1, a. i. 'Wikipedia'
920 4582
works even when you split up stream into say 32k bytes, and do the mod
transform between each stream, and the single number reduction at the end.
([: ({: , [: <: +/) +/\)"1 ] _4 ]/ 1, a. i. 'Wikipedia'
920 4582
----- Original Message -----
From: bill lam <[email protected]>
To: Programming forum <[email protected]>
Cc:
Sent: Sunday, August 24, 2014 7:35:26 AM
Subject: Re: [Jprogramming] Adler-32
I realized that my loop translation solution was equally faulty in its
final step. It should be
({: (23 b.) 16&(33 b.)@{.) s2,s1
On Aug 24, 2014 6:40 PM, "bill lam" <[email protected]> wrote:
> J32 should give a 32-bit integer so that the last train
> should be
> [: ({: (23 b.) 16&(33 b.)@{.)
> instead of
> 65536#.
>
> This shoud be good enough. Thanks.
>
> Вс, 24 авг 2014, Jan-Pieter Jacobs написал(а):
> > You could incorporate the modulo operation in the summation directly:
> >
> > As per Raul's solution, with the modulo addition:
> >
> > a32_2=: 65536#. _1 0+ [:((65521|+)/ , {.) [: (65521|+)/\. 1,~ a.i. |.
> > NB. Test on 10M of random data
> > Randdata =: a.{~ ?10000000$256
> > timespacex 'r1=:a32_2 Randdata'
> > 7.26671 2.68438e8
> >
> > timespacex 'r1=:adler32 Randdata'
> > 36.2094 2.01333e8
> >
> > Jan-Pieter
> >
> > 2014-08-24 11:14 GMT+02:00 bill lam <[email protected]>:
> > > Since s2 is quadratic, it overflows quickly in J32. However
> > > ieee floating points have 52 bits mantissa, so it can still
> > > give correct result for medium size data albeit overflowed.
> > >
> > > 9!:11[16
> > > (3!:0;]) a32 1e6{.a.
> > >
> > > Вс, 24 авг 2014, Raul Miller написал(а):
> > >> Hmm... actually there might be a floating point overflow problem for
> > >> gigabyte length arguments. I do not have the patience, however, to
> > >> find what (for example) adler32 1e9#{:a. is.
> > >>
> > >> Thanks,
> > >>
> > >> --
> > >> Raul
> > >>
> > >>
> > >>
> > >> On Sun, Aug 24, 2014 at 4:37 AM, Raul Miller <[email protected]>
> 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 <[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,
> > >> >> ====================================================
> > >> >> GPG key 1024D/4434BAB3 2008-08-24
> > >> >> gpg --keyserver subkeys.pgp.net --recv-keys 4434BAB3
> > >> >> gpg --keyserver subkeys.pgp.net --armor --export 4434BAB3
> > >> >>
> ----------------------------------------------------------------------
> > >> >> For information about J forums see
> http://www.jsoftware.com/forums.htm
> > >> ----------------------------------------------------------------------
> > >> For information about J forums see
> http://www.jsoftware.com/forums.htm
> > >
> > > --
> > > regards,
> > > ====================================================
> > > GPG key 1024D/4434BAB3 2008-08-24
> > > gpg --keyserver subkeys.pgp.net --recv-keys 4434BAB3
> > > gpg --keyserver subkeys.pgp.net --armor --export 4434BAB3
> > > ----------------------------------------------------------------------
> > > For information about J forums see http://www.jsoftware.com/forums.htm
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
>
> --
> regards,
> ====================================================
> GPG key 1024D/4434BAB3 2008-08-24
> gpg --keyserver subkeys.pgp.net --recv-keys 4434BAB3
> gpg --keyserver subkeys.pgp.net --armor --export 4434BAB3
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
