-1

Ok, I need a bit of help from my Math/Computer geeks out there. In the curse of an optimization for a program I am writing in Python, I found the following problem: for a given byte value, I need to get an arbitrary number of those bytes consecutives within another numeric variable.

This is very easy to do with iterations, let's say:

byte = 0x0f
reps = 3
result = 0
    for i in range(0, reps):
        result = (result << 8) | byte

(Note that result << 8 is the same than result * 256, though sometimes is faster. I don't know if this is the case with Python, actually, maybe the language processor itself is able to do that conversion before compiling)

I haven't tested that code, but it should work. For the given byte and number of repetitions it should give a result of 0x0f0f0f

Now, the problem is that I am convinced that there has to be way to obtain such result WITHOUT iterating through a loop. I think there should be an arithmetic relation between the byte value and the number of reps, so I could be able to obtain that result with the need of iterating.

But after several hours struggling with this, I have not been able to found such, even when I have this in front of my face with those damn numbers laughing at me:

hex(0x0f * (2**24 + 2**16 + 2**8 + 1))
'0xf0f0f0f'

There have to be a general way to find that 

(2**24 + 2**16 + 2**8 + 1)

multiplier based on the number of reps (it his case it is for three repetitions, for two you should remove 

2**24 +

and for four you should add 

2**32 +

at the start), instead of iterating. There's a clear relation between those exponentials, so IT HAS TO BE A WAY THERE SOMEWHERE CONCEALED TO MY EYES!!!

Any hints are very welcomed... Even one demonstrating the impossibility of doing want I what to do without a loop.

PS. Excuse my lack of Math skills, that's why my example is a program in Python instead a Mathematical expression that I think would have fit better here.

Fran Marzoa
  • 101
  • Your problem is you're trying to optimize python code by converting a loop to some bit arithmetic. This will not have a significant effect on your python code. If you need to optimize such things, rewrite that module as a DLL in C++ or D and use ctypes to call it, or use CFFI. I found that rendering a set of 100 images of an LED glow effect in python seemed to take hours, while the same algo written as a C module finished in under a minute. I'm not dis'ing python. In fact I'm using it right now to write a PyQt5 app with a lot of graphics. Everything runs great! Except for the LED glow. – Daniel Donnelly Mar 12 '16 at 20:56
  • Well, take a look at this:

    https://upload.wikimedia.org/math/8/c/1/8c13104b74e13a61a0beb44fa8d6e46b.png

    Let's say n=1,000,000, so you can either use the approach at the right of the equal symbol, and hence do a loop with 1,000,000 iterations, or use the one at the left of the equal symbol, and have it done with just one arithmetic calculation. Which approach you think it would be faster?

     – Fran Marzoa Mar 12 '16 at 20:58
  • 1
    @Fran yes, for that specific problem, the $n(n+1)/2$ formula would work a lot faster :) – Daniel Donnelly Mar 12 '16 at 21:00

3 Answers3

3

You have a geometric series. You can use the fact that $1+2^8+2^{16}+2^{24}=\frac {2^{32}-1}{2^8-1}$ If you change the number of terms, the only thing that changes is the $32$ exponent.

Ross Millikan
  • 374,822
  • Now, that's great. If that works, it is exactly what I was looking for. I knew there had to be way! It seems that for calculating such exponent I just have to multiply the number of repetitions + 1 by 8, which is a really trivial operation. – Fran Marzoa Mar 12 '16 at 21:08
  • Tested and working great, even for huge numbers. I owe you two daughters and four camels! ;) – Fran Marzoa Mar 12 '16 at 21:10
  • @Fran: If you are working with floats, remember that you have just 53 bits in the mantissa, so you are then (implicitly) working with a bounded number of repetitions... – copper.hat Mar 12 '16 at 21:11
  • @copper.hat no problem with that, I am only working with integers. :) – Fran Marzoa Mar 12 '16 at 21:12
  • 1
    This approach will fail if you want to fill the int with your bytes and you don't have a bigger int available. If you want to fill a $32$ bit int, it would call for $\frac {2^{40}-1}{2^8-1}$ and you can't do $2^{40}$ unless you have $64$ bit ints available. As long as you are not filling the highest byte you are OK. The math is fine, your computer is stupid. – Ross Millikan Mar 12 '16 at 21:21
  • That division will always return an integer. Don't ask me to demonstrate why, probably @Ross Millikan could, but if you try substituting the exponent 32 for whatever multiple of 8 you want, the modulus of such division will always be 0. – Fran Marzoa Mar 12 '16 at 21:22
  • 1
    It is demonstrated in the Wikipedia article that this division always results in an integer, coming from polynomial division of the expression. – Ross Millikan Mar 12 '16 at 21:24
  • @RossMillikan no problem with that, man. Python would choose a numeric type that fits the result "authomagically". I have checked it using exponents as big as 1024, that will never be used in practice. – Fran Marzoa Mar 12 '16 at 21:24
  • @cooper.hat maybe that's true, but as told, for most cases (99% or so) the result will fit into a normal 64 bit integer, and if you have to use a long with this approach, you will have to use it also with the loop based approach, so in this case at least you will get rid of one loop. Anyway, I will do some benchmark testing. – Fran Marzoa Mar 12 '16 at 21:26
1

It is not entirely clear what you are looking for.

If the number of repetitions is fixed, then you can precompute one number and use this to find the 'repetition number' by just using multiplication.

Suppose you need $r$ repetitions, form the number $n = \sum_{k=0}^{r-1} 2^{8k}$. Then, to repeat the byte $b$, form the number $nb$.

Addendum:

In Python 3.2+ it would be something like int.from_bytes(bytearray(chr(b)*r,'utf-8'),byteorder='little'), where b is the byte and r the repetitions.

copper.hat
  • 172,524
  • Hi, thanks for your answer. The number of repetitions may vary. I think that for using a summation I need to rely on a loop, what's what I am trying to avoid if I can. What I am looking for is someway to obtain the number n without using a loop (or summation, for the matter). It well maybe there is no such a way, anyway. I am not sure. Sorry for the confusion. – Fran Marzoa Mar 12 '16 at 20:43
  • 1
    Well, somewhere a loop is involved, I guess your question is whether it is explicit or not? – copper.hat Mar 12 '16 at 20:44
  • What version of Python are you using? – copper.hat Mar 12 '16 at 20:45
  • I understand that with that approach a loop is involved, but I wonder whether there would be a different equivalent approach not involving a loop. You know, like in this case:

    https://upload.wikimedia.org/math/8/c/1/8c13104b74e13a61a0beb44fa8d6e46b.png

     – Fran Marzoa Mar 12 '16 at 20:48
  • I am using Python 2.7 – Fran Marzoa Mar 12 '16 at 20:49
  • Bummer, in 3+ it would be something like int.from_bytes(bytearray(chr(b)*r,'utf-8'),byteorder='little'), where b is the byte and r the repetitions. – copper.hat Mar 12 '16 at 20:50
  • I must reckon that's a killer one liner, but still involves a loop, and even a byte array. In most practical cases the resulting "n" won't be bigger than a 64 bit integer, so they should fit well in a long, and Python will take care of storing them in a longer number in the few cases it will be necessary. – Fran Marzoa Mar 12 '16 at 20:54
  • If $r$ (repetitions) is variable, you cannot avoid a loop without going the real computation (as in $\mathbb{R}$) route... – copper.hat Mar 12 '16 at 20:56
  • I am not sure whether that's true. Consider this case:

    https://upload.wikimedia.org/math/8/c/1/8c13104b74e13a61a0beb44fa8d6e46b.png

    There n is variable, but nonetheless it could be expressed as an arithmetic operation that doesn't involve loops at all. Obviously my case is different, and maybe what's applicable in that case is no way applicable to my very own one, indeed.

     – Fran Marzoa Mar 12 '16 at 21:01
  • 1
    Look at Ross' answer, this is what I mean by real computation. You can do this (to compute the $n$ above), but you need to ensure that the computed number is the correct integer and then multiply by $b$. – copper.hat Mar 12 '16 at 21:03
  • To belabour the point, if you use arbitrary precision integer arithmetic, you are implicitly using a loop somewhere. When you compute ${2^{8(n+1)}-1 \over 2^8 -1}$, there must be a loop somewhere since $n$ is arbitrary. That is what I meant in my second comment above. – copper.hat Mar 12 '16 at 21:21
0

In Python, we can take advantage of string formatting. I'll use string interpolation here:

>>> b = 0x2a
>>> reps = 3
>>> '0x' + ('%02x' % b) * reps
'0x2a2a2a'
Adriano
  • 41,576
  • Thanks! but that still involves a loop, also string to integer conversion -and vice versa- would add more load to the algorithm. – Fran Marzoa Mar 12 '16 at 20:52