Results 1 to 4 of 4
Like Tree3Thanks
  • 2 Post By earboth
  • 1 Post By earboth

Math Help - Math help to speed up algorithm

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    USA
    Posts
    2

    Question Math help to speed up algorithm

    Hello.

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

    Math help to speed up algorithm-1.gif

    or

    Math help to speed up algorithm-2.gif

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


    1. Click image for larger version. 

Name:	1.gif 
Views:	18 
Size:	272 Bytes 
ID:	25773 | Math help to speed up algorithm-1.gif
    2. Math help to speed up algorithm-3.gif | Math help to speed up algorithm-2.gif
    3. Math help to speed up algorithm-4.gif | Math help to speed up algorithm-3.gif
    4. Math help to speed up algorithm-5.gif | Math help to speed up algorithm-4.gif
    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,804
    Thanks
    115

    Re: Math help to speed up algorithm

    Quote Originally Posted by skycrter View Post
    Hello.

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

    Click image for larger version. 

Name:	1.gif 
Views:	18 
Size:	272 Bytes 
ID:	25773

    or

    Click image for larger version. 

Name:	2.gif 
Views:	17 
Size:	421 Bytes 
ID:	25774

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


    1. Click image for larger version. 

Name:	1.gif 
Views:	18 
Size:	272 Bytes 
ID:	25773 | Click image for larger version. 

Name:	1.gif 
Views:	17 
Size:	180 Bytes 
ID:	25778
    2. Click image for larger version. 

Name:	3.gif 
Views:	17 
Size:	558 Bytes 
ID:	25775 | Click image for larger version. 

Name:	2.gif 
Views:	17 
Size:	439 Bytes 
ID:	25779
    3. Click image for larger version. 

Name:	4.gif 
Views:	1 
Size:	714 Bytes 
ID:	25776 | Click image for larger version. 

Name:	3.gif 
Views:	1 
Size:	625 Bytes 
ID:	25780
    4. Click image for larger version. 

Name:	5.gif 
Views:	1 
Size:	903 Bytes 
ID:	25777 | Click image for larger version. 

Name:	4.gif 
Views:	2 
Size:	748 Bytes 
ID:	25781
    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
    Thanks from topsquark and skycrter
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,804
    Thanks
    115

    Re: Math help to speed up algorithm

    Quote Originally Posted by skycrter View Post
    Hello.

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

    Click image for larger version. 

Name:	1.gif 
Views:	18 
Size:	272 Bytes 
ID:	25773

    or

    Click image for larger version. 

Name:	2.gif 
Views:	17 
Size:	421 Bytes 
ID:	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^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
    Last edited by earboth; November 18th 2012 at 09:56 AM.
    Thanks from skycrter
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2012
    From
    USA
    Posts
    2

    Re: Math help to speed up algorithm

    Thank you, earboth.


    Your two solutions help perfectly.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: October 21st 2012, 12:51 PM
  2. Replies: 1
    Last Post: June 19th 2010, 10:05 PM
  3. final speed from escape speed
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: November 21st 2009, 01:23 PM
  4. angular speed, tangetial speed.
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: November 24th 2007, 10:31 AM
  5. Converting horizontal speed to vertical speed
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: July 27th 2006, 06:23 AM

Search Tags


/mathhelpforum @mathhelpforum