add_new() for array like push_back() for vector

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • John Harrison

    #16
    Re: vector.reserve( ) and performance (Was: add_new() for array like push_back() for vector)

    >[color=blue]
    > I wanted
    > * to check what (and how fast) can we compute when using _explicit_[/color]
    Fibonacci formula,[color=blue]
    > * to create and to test class BigInt,
    > * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only[/color]
    Fibonaccci[n])[color=blue]
    >[/color]

    Another possible optimization, replace

    default :
    fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
    break;

    with

    default :
    fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
    break;

    When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have
    been calculated and stored so this is safe to do. Might save a little time
    and can't do any harm.

    Actually my intuition is that it will not save any significant time, but
    worth a try.

    john


    Comment

    • John Harrison

      #17
      Re: vector.reserve( ) and performance (Was: add_new() for array like push_back() for vector)

      >[color=blue]
      > I wanted
      > * to check what (and how fast) can we compute when using _explicit_[/color]
      Fibonacci formula,[color=blue]
      > * to create and to test class BigInt,
      > * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only[/color]
      Fibonaccci[n])[color=blue]
      >[/color]

      Another possible optimization, replace

      default :
      fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
      break;

      with

      default :
      fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
      break;

      When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have
      been calculated and stored so this is safe to do. Might save a little time
      and can't do any harm.

      Actually my intuition is that it will not save any significant time, but
      worth a try.

      john


      Comment

      • Alex Vinokur

        #18
        Re: vector.reserve( ) and performance (Was: add_new() for array like push_back() for vector)


        "John Harrison" <john_andronicu s@hotmail.com> wrote in message news:c5an40$2nj 0mp$1@ID-196037.news.uni-berlin.de...[color=blue][color=green]
        > >
        > > I wanted
        > > * to check what (and how fast) can we compute when using _explicit_[/color]
        > Fibonacci formula,[color=green]
        > > * to create and to test class BigInt,
        > > * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only[/color]
        > Fibonaccci[n])[color=green]
        > >[/color]
        >
        > Another possible optimization, replace
        >
        > default :
        > fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
        > break;
        >
        > with
        >
        > default :
        > fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
        > break;
        >
        > When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have
        > been calculated and stored so this is safe to do. Might save a little time
        > and can't do any harm.
        >
        > Actually my intuition is that it will not save any significant time, but
        > worth a try.
        >
        > john
        >
        >[/color]

        I have tested that.
        It is unclear if it saves some time, but indeed it does no harm.
        I am going to use
        * fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));

        P.S. That was one of options in very old algorithm :
        http://groups.google.com/groups?selm...40smc.vnet.net (method getFibNumber (int n_i)).

        --
        Alex Vinokur
        mailto:alexvn@c onnect.to








        Comment

        • Alex Vinokur

          #19
          Re: vector.reserve( ) and performance (Was: add_new() for array like push_back() for vector)


          "John Harrison" <john_andronicu s@hotmail.com> wrote in message news:c5an40$2nj 0mp$1@ID-196037.news.uni-berlin.de...[color=blue][color=green]
          > >
          > > I wanted
          > > * to check what (and how fast) can we compute when using _explicit_[/color]
          > Fibonacci formula,[color=green]
          > > * to create and to test class BigInt,
          > > * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only[/color]
          > Fibonaccci[n])[color=green]
          > >[/color]
          >
          > Another possible optimization, replace
          >
          > default :
          > fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
          > break;
          >
          > with
          >
          > default :
          > fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
          > break;
          >
          > When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have
          > been calculated and stored so this is safe to do. Might save a little time
          > and can't do any harm.
          >
          > Actually my intuition is that it will not save any significant time, but
          > worth a try.
          >
          > john
          >
          >[/color]

          I have tested that.
          It is unclear if it saves some time, but indeed it does no harm.
          I am going to use
          * fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));

          P.S. That was one of options in very old algorithm :
          http://groups.google.com/groups?selm...40smc.vnet.net (method getFibNumber (int n_i)).

          --
          Alex Vinokur
          mailto:alexvn@c onnect.to








          Comment

          Working...