# Thread: Math help to speed up algorithm

1. ## Math help to speed up algorithm

Hello.

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

or

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

1. |
2. |
3. |
4. |
5. and so on...

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.

2. ## Re: Math help to speed up algorithm

Originally Posted by skycrter
Hello.

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

or

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

1. |
2. |
3. |
4. |
5. and so on...

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 $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) ........ $\rightarrow$ 0 factor ........ $\rightarrow$ -2^0 = -1

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

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

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

3. Add the constant results: -99

Thus

$((((((((((x*2)-1)*2)-1)*2)*2)*2)*2)-1)*2)-1 = 2^7 \cdot x - 99$

3. ## Re: Math help to speed up algorithm

Originally Posted by skycrter
Hello.

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

or

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 $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:

$((((((((((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$

4. ## Re: Math help to speed up algorithm

Thank you, earboth.