Re: fast bit rotation
- Posted by "Kat" <gertie at visionsix.com> Dec 31, 2003
- 445 views
On 31 Dec 2003, at 15:59, Pete Lomax wrote: > > > Another thing you could try is to build tables of pre-computed shifts, > eg: > > sequence shl, shr > shl=repeat(0,256) > shr=repeat(0,256) > for i = 0 to 255 do > if i<=127 then > shl[i+1]=i*2 > else > shl[i+1]=and_bits(i,#7F)*2+1 > end if > shr[shl[i+1]+1]=i > end for > > Use k=shl[k+1] when k is 0..255, to avoid zero index problems. > > You can do your own test/timings, though I got 3.9 million/sec on a > 233MHz PII with 48Mb ram, sorry Tommy, CNR ) But those are bytes, not 31 (or 32) bit full integers. When scaled up: sequence shl, shr atom time1, time2, int int = 65535 * 256 ---- 16776960 shl=repeat(0,65536*256) shr=repeat(0,65536*256) time1 = time() for i = 0 to int do if i<=127 then shl[i+1]=i*2 else shl[i+1]=and_bits(i,#7F)*2+1 end if shr[shl[i+1]+1]=i end for time2 = time() puts(1,sprintf("%d",time2-time1)) time1 = getc(0) i got 29 sec for that run, or 578,515 shifts per sec, on a K6-2-233 with 384 megs of ram. Good thing i had the ram, too, because the program used over 131 megabytes of ram. It used 87% of cpu clocks running on win95B. Kat