I'm having a hard time getting a streaming version (one that works on parts of
the data and then recombines.
can only do 4096 bytes for 32 bit J, before it needs do call |.. but it is
fast, and 64bit J can do 2^32 larger byte sizes (over 16TB)
timespacex ' (65521 | [: ({: , [: <: +/) +/\) 1 ,~ Randdata'
0.187033 2.68442e8
the block I have with a streaming (chunk) version is how to get these numbers
+/\ 1 87 105 107 105 112 101 100 105 97
1 88 193 300 405 517 618 718 823 920
from numbers in this shape:
_3 [\ 1, a. i. 'Wikipedia'
1 87 105
107 105 112
101 100 105
97 0 0
, is not allowed. The key point about 1 88 193 300 405 517 618 718 823 920 is
that it provides the basis for s2
<: +/ 1 88 193 300 405 517 618 718 823 920
4582
----- Original Message -----
From: 'Pascal Jasmin' via Programming <[email protected]>
To: "[email protected]" <[email protected]>
Cc:
Sent: Sunday, August 24, 2014 11:48:23 AM
Subject: Re: [Jprogramming] Adler-32
sorry that version doesn't work on a stream. will post one later.
----- Original Message -----
From: bill lam <[email protected]>
To: 'Pascal Jasmin' via Programming <[email protected]>
Cc:
Sent: Sunday, August 24, 2014 11:15:57 AM
Subject: Re: [Jprogramming] Adler-32
Did you mean _4]\ ?
Anyway, from the wikipedia page,
B = (1 + D[1]) + (1 + D[1] + D[2]) + ... + (1 + D[1] + D[2] + ... + D[n]) (mod
65521)
= n×D[1] + (n−1)×D[2] + (n−2)×D[3] + ... + D[n] + n (mod 65521)
if a parallel version is asked for, probably the formula in the
2nd line should be used, then the speed may increase directly
proportional to the number of core. A good problem for Nvidia
Jetson Tk1 board with 192 CUDA cores.
* http://www.nvidia.com/object/jetson-tk1-embedded-dev-kit.html
NB. =============================
NB. Raul Miller
a32=: [: ({: (23 b.) 16&(33 b.)@{.) _1 0 + [: ((65521 | +)/ , {.) [: (65521 |
+)/\. 1 ,~ a. i. |.
NB. from zlib rfc
adler32=: 3 : 0
's1 s2'=. 1 0
for_a. a.i.y do.
s1=. 65521 | s1 + a
s2=. 65521 | s2 + s1
end.
({: (23 b.) 16&(33 b.)@{.) s2,s1
)
NB. formula from adler32 wikipedia
adler32a=: 3 : 0
dat=. a.i.y
s1=. (65521|+)/1,dat
s2=. (#dat) (65521|+) (65521|+)/ (}:i.(-1+#dat)) (65521|*) dat
({: (23 b.) 16&(33 b.)@{.) s2,s1
)
f=: 1e6{.a.
smoutput adler32 f
smoutput adler32a f
smoutput a32 f
smoutput timespacex'adler32 f'
smoutput timespacex'adler32a f'
smoutput timespacex'a32 f'
NB. =============================
result on J32
_121519079
_121519079
_121519079
3.99429 4.19898e6
1.03239 2.09744e7
0.9106 8.38976e6
Вс, 24 авг 2014, jprogramming написал(а):
> 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
--
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
