# Math help to speed up algorithm

• Nov 17th 2012, 10:14 PM
skycrter
Math help to speed up algorithm
Hello.

Simply I have a C++ algorithm that performs two types of simple computations randomly and consecutively:

Attachment 25773

or

Attachment 25774

being "x" the result of the previous computation, example:

The problem is that, after a set of computations, normally the machine gets tired, because the result number grows very fast.
I'm working with very great integers, biggest than (2^1000). To help it I'm trying to work only with notations, but I'm having problems
with the second computation case, id est, "(x*2)-1". For example, I can write: "(((((x*2)*2)*2)*2)*2)*2 = x * 2^6", this means the machine
can handle very great integers only incrementing "1" to the exponent. However, when the second computation case arises, I don't know how to proceed, that is,
I don't know how I can shrink [for instance]: ((((((((((x*2)-1)*2)-1)*2)*2)*2)*2)-1)*2)-1 so that to avoid multiplications like the first case. The problem lies in the randomness of "-1".
Sorry if I'm ignoring something obvious.

Then, there's a way through which I can write "((((((((((x*2)-1)*2)-1)*2)*2)*2)*2)-1)*2)-1" in notation form without having to resort to "brute force"?

Very thanks.
• Nov 17th 2012, 11:07 PM
earboth
Re: Math help to speed up algorithm
Quote:

Originally Posted by skycrter
Hello.

Simply I have a C++ algorithm that performs two types of simple computations randomly and consecutively:

Attachment 25773

or

Attachment 25774

being "x" the result of the previous computation, example:

The problem is that, after a set of computations, normally the machine gets tired, because the result number grows very fast.
I'm working with very great integers, biggest than (2^1000). To help it I'm trying to work only with notations, but I'm having problems
with the second computation case, id est, "(x*2)-1". For example, I can write: "(((((x*2)*2)*2)*2)*2)*2 = x * 2^6", this means the machine
can handle very great integers only incrementing "1" to the exponent. However, when the second computation case arises, I don't know how to proceed, that is,
I don't know how I can shrink [for instance]: ((((((((((x*2)-1)*2)-1)*2)*2)*2)*2)-1)*2)-1 so that to avoid multiplications like the first case. The problem lies in the randomness of "-1".
Sorry if I'm ignoring something obvious.

Then, there's a way through which I can write "((((((((((x*2)-1)*2)-1)*2)*2)*2)*2)-1)*2)-1" in notation form without having to resort to "brute force"?

Very thanks.

Not sure if this helps:

1. Count the number of factor 2. In your example you have 7 factors 2. So the result starts with $\displaystyle 2^7 \cdot x$

2. To determine the constant summand you parse the term from the end to the beginning:

Start at the end and count the number of factors 2 until you reach the next (-1) ........ $\displaystyle \rightarrow$ 0 factor ........ $\displaystyle \rightarrow$ -2^0 = -1

Start at the end and count the number of factors 2 until you reach the next (-1) ........ $\displaystyle \rightarrow$ 1 factor ........ $\displaystyle \rightarrow$ -2^1 = -2

Start at the end and count the number of factors 2 until you reach the next (-1) ........ $\displaystyle \rightarrow$ 5 factor ........ $\displaystyle \rightarrow$ -2^5 = -32

Start at the end and count the number of factors 2 until you reach the next (-1) ........ $\displaystyle \rightarrow$ 6 factor ........ $\displaystyle \rightarrow$ -2^6 = -64

3. Add the constant results: -99

Thus

$\displaystyle ((((((((((x*2)-1)*2)-1)*2)*2)*2)*2)-1)*2)-1 = 2^7 \cdot x - 99$
• Nov 18th 2012, 04:03 AM
earboth
Re: Math help to speed up algorithm
Quote:

Originally Posted by skycrter
Hello.

Simply I have a C++ algorithm that performs two types of simple computations randomly and consecutively:

Attachment 25773

or

Attachment 25774

being "x" the result of the previous computation, example:

...
Then, there's a way through which I can write "((((((((((x*2)-1)*2)-1)*2)*2)*2)*2)-1)*2)-1" in notation form without having to resort to "brute force"?

Very thanks.

I've found - so I hope - a very simple way to transform your term:

1. Count the number of factor 2. In your example it is 7. So you'll have $\displaystyle 2^7x$.

2. Count how often (-1) and the factor 2 occur. If both values are simultaneously present write 1, if only the factor 2 is present write 0. In your example you'll get 1100011.

This is the binary notation of the decimal value of 99.

3. In short:

$\displaystyle ((((((((((x \underbrace{*2)-1}_{1})\underbrace{*2)-1}_{1})\underbrace{*2}_{0})\underbrace{*2}_{0}) \underbrace{*2}_{0})\underbrace{*2)-1}_{1})\underbrace{*2)-1}_{1}=2^7 x - 1100011_b$
• Nov 18th 2012, 03:32 PM
skycrter
Re: Math help to speed up algorithm
Thank you, earboth.

Your two solutions help perfectly.