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

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

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

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

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

3. Add the constant results: -99

Thus

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 .

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:

Re: Math help to speed up algorithm

Thank you, earboth.

Your two solutions help perfectly.