9 Attachment(s)

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:

- Attachment 25773 | Attachment 25778
- Attachment 25775 | Attachment 25779
- Attachment 25776 | Attachment 25780
- Attachment 25777 | Attachment 25781
- 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.

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:

- Attachment 25773 | Attachment 25778
- Attachment 25775 | Attachment 25779
- Attachment 25776 | Attachment 25780
- Attachment 25777 | Attachment 25781
- 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 $\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$

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$

Re: Math help to speed up algorithm

Thank you, earboth.

Your two solutions help perfectly.