[Numpy-discussion] binary shift for ndarray

[Robert Kern]

On Wed, May 20, 2009 at 14:46, dmitrey <dmitrey.kroshko at scipy.org> wrote:
> On May 20, 10:34 pm, Robert Kern <robert.k... at gmail.com> wrote:
>> On Wed, May 20, 2009 at 14:24, dmitrey <dmitrey.kros... at scipy.org> wrote:
>> > hi all,
>>
>> > suppose I have A that is numpy ndarray of floats, with shape n x n.
>>
>> > I want to obtain dot(A, b), b is vector of length n and norm(b)=1, but
>> > instead of exact multiplication I want to approximate b as a vector
>> > [+/- 2^m0, ± 2^m1, ± 2^m2 ,,, ± 2^m_n], m_i are integers, and then
>> > invoke left_shift(vector_m) for rows of A.
>>
>> You don't shift floats. You only shift integers. For floats,
>> multiplying by an integer power of 2 should be fast because of the
>> floating point representation (the exponent just gets incremented or
>> decremented), so just do the multiplication.
>>
>> > So, what is the simplest way to do it, without cycles of course? Or it
>> > cannot be implemented w/o cycles with current numpy version?
>>
>> It might help if you showed us an example of an actual b vector
>> decomposed the way you describe. Your description is ambiguous.
>>
>> --
>> Robert Kern
>
> For the task involved (I intend to try using it for speed up ralg
> solver) it doesn't matter essentially (using ceil, floor or round),
> but for example let m_i is
> floor(log2(b_i)) for b_i > 1e-15,
> ceil(log2(-b_i)) for b_i < - 1e-15,
> for - 1e-15 <= b_i <= 1e-15 - don't modify the elements of A related
> to the b_i at all.

I strongly suspect that a plain dot(A, b) will be faster than doing
all of that. With a little bit of work with frexp() and ldexp(), you
could probably do those floor(log2())'s cheaply, but ultimately, you
will still need to do a dot(A, b_prime) at the end. There is no
bit-shift operation available for floats (anywhere, not just numpy);
you have to form the float corresponding to +-2**m and multiply. If
you had many A-matrices and a static b-vector, you might see a tiny
improvement because all of the b_prime elements were exactly of the
form +-2**m, but I doubt it.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless
enigma that is made terrible by our own mad attempt to interpret it as
though it had an underlying truth."
  -- Umberto Eco