469,649 Members | 1,574 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,649 developers. It's quick & easy.

Efficient custom checksum of one-dim numpy arrays of uint16

Hi,

This is my first post here, I am looking forward to being here.

I have actually posted almost the same question on comp.lang.python:

http://groups.google.dk/group/comp.l...eae3719c6e3fe8

and got some hints at what i could do, but it is a little bit too complicated for me (yet), and i was wondering if there is a simpler way to do this.

I have implemented two functions for making a complementary ones addition of uint16 one-dimensional arrays, because I need this for computing a checksum on very many arrays with 50-10000 elements (difrerent size for each array)

Here it goes

from numpy import *

def compl_add_uint16(a, b):
c = a + b
c += c >> 16
return c & 0xFFFF

def compl_one_checksum(uint16s):
return reduce(compl_add_uint16, uint16s, 0x0000)

This works correct, but it is also *the* bottleneck in the several ksloc apllication as 88% of the time is spend doing the reduce, and 95% of that time is spend in the compl_add_uint16 function.

I does not surprise me that it is slow as the interpreter has to walk through the three lines in compl_add_uint on each addition.

However, i cannot figure out how to make it the right pythonic and efficient way?

I prefer a pure numpy implementation, but I am also willing to go into some weave inlining and blitz, although I have never tried that before and I do not have a blitz compatible C++ compiler installed on my MS Server 2003 OS.

How can I make that faster?

From looking around it seems like i need to go in some ufunc reduce direction to do this the numpy way, but how?

Thank you for you time,

-- Slaunger
Nov 15 '08 #1
1 3214
I got the answer on comp.python.numeric.general from Charles R. Harris.

This does the trick:
Expand|Select|Wrap|Line Numbers
  1. def complement_add_uint16(x) :
  2.     y = sum(x, dtype=uint64)    
  3.     while y >= 2**16 :
  4.         y = (y & uint64(0xffff)) + (y >> uint64(16))
  5.     return y
  6.  
That just boosted my checksum processing speed from 413 kB/s to, hold on, 47400 kB/s, which is more than a 100-fold increase. numpy rules!

-- Slaunger
Nov 15 '08 #2

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

12 posts views Thread by Mercuro | last post: by
6 posts views Thread by pmatos | last post: by
2 posts views Thread by s.subbarayan | last post: by
reply views Thread by Chua Wen Ching | last post: by
5 posts views Thread by Christopher Kimbell | last post: by
1 post views Thread by =?Utf-8?B?YmlsbCB0aWU=?= | last post: by
reply views Thread by gheharukoh7 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.