Numbers viewed as binary sequences
2 posts
• Page 1 of 1
Numbers viewed as binary sequences
I am trying to write some random number generation code using Marsaglia's Complementary Multiply-With-Carry algorithms (http://en.wikipedia.org/wiki/Multiply-with-carry). This requires a lot of simple arithmetic and binary calculations, like this in C:
Anyone developing efficient routines for performing logical functions on decimal floats? Better way to have one's cake (fast arithmetic) and eat it too (binary views)?
t = a * Q[ i ] + c; c = (t >> 32);The key is that it requires numbers like t to be "long long," i.e. 64-bit, numbers. An easy way to do this is to use decimal floats (⎕DR of 1287), which are great for up to 34-digit integer arithmetic. So far so good. The problem is you can't simply use 11 ⎕DR ... sequences to get and set bits, since the internal structure of decimal floats disallows some bit combinations. So, I wrote a dfn operator called binDF (binary decimal float) that uses encode-decode to manage conversions to valid sequences, allowing such things as the above to be coded in APL as (where > calculates a C binary shift >>):
t←a×Q[ i ]+c ⋄ c← t >binDF 32and similarly c as exclusive-or of integers a and b would be:
c←a ≠binDF bThe problem is that the dfn is very slow, presumably because of all the setup required and possibly the use of (⊥⍣¯1), so a test algorithm for 32-bit binary integers using ⎕DR appears to be an order of magnitude or more faster than the dfn (ignoring the arithmetic, which is not the bottleneck). My only recourse is to pull apart the handy dfn and put all the setup in the higher routine, possibly to check for numbers that fit into 32 bits, etc. etc. (making fast code that's not elegant or readable).
Anyone developing efficient routines for performing logical functions on decimal floats? Better way to have one's cake (fast arithmetic) and eat it too (binary views)?
- petermsiegel
- Posts: 143
- Joined: Thu Nov 11, 2010 11:04 pm
Re: Numbers viewed as binary sequences
You'll find that
Don't make the mistake of thinking that
{((1+⌊⍺⍟⍵)⍴⍺)⊤⍵}is usually several times quicker than
(⊥⍣¯1)'though I don't know what part of your total processing that constitutes. There may also be issues with zero or negative ⍵ that can be overcome with
{((1+⌊⍺⍟(⍵=0)+⍵+(⍵<0)×1-2×⍵)⍴⍺)⊤⍵}that takes little extra time but no point if it doesn't arise. Also I don't know if your calculation is in an array or simple scalar context mine working only on simple scalars and requiring a max on the left argument of ⊤ otherwise.
Don't make the mistake of thinking that
{1+⌊⍺⍟⍵}is the same as
{⌈⍺⍟⍵}because it fails when ⍵ is an integer power of ⍺. The former is required.
-
Phil Last - Posts: 628
- Joined: Thu Jun 18, 2009 6:29 pm
- Location: Wessex
2 posts
• Page 1 of 1
Who is online
Users browsing this forum: No registered users and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group