Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #37132

Re: What practice can get speed improvement in C++?

Show all headers | View raw

On 16.07.2015 20:16, Öö Tiib wrote:
>> A type. It can be uint64_t, uint1024_t from boost or relay
>> big integer from GMP. What do you like and need. It doesn't matter.
>
> Factorial algorithms for arbitrary precision integer are different beast
> entirely. Those can take some time.

I have never saw one.



>> The point is: a simple recursion will be optimized to loop. For more
>> complex case it is hard. For example you can write quicksort as a loop
>> (using small stack for division points), it isn't even that hard, but
>> still most implementations (including standard library) use recursion.
>> Can you write extended euclidean algorithm (simple algorithm from
>> school:) as loop?
>
> It has been usually described as simple loop? Pseudo-code from wikipedia:
>
>      function extended_gcd(a, b)
>          s := 0;    old_s := 1
>          t := 1;    old_t := 0
>          r := b;    old_r := a
>          while r ≠ 0
>              quotient := old_r div r
>              (old_r, r) := (r, old_r - quotient * r)
>              (old_s, s) := (s, old_s - quotient * s)
>              (old_t, t) := (t, old_t - quotient * t)
>          output "Bézout coefficients:", (old_s, old_t)
>          output "greatest common divisor:", old_r
>          output "quotients by the gcd:", (t, s)

Heh, dementia;-] I was sure wiki have recursive version,
what other source could I have used to write that (as an
argument for usefulness of tuple) ;-)

tuple<int, int, int> egcd(int a,int b)
{ //return  {gcd, x, y}; a*x+b*y = gcd;

	if (b==0)
		return make_tuple(a,1,0);
	else
	{
		int g,x,y;
		tie(g,y,x) = egcd(b,a%b);
		return make_tuple(g,x, y - ((a / b)) * x);
	}
}

Getting the first version from the second isn't as hard a I thought,
but still not trivial.


>> I think of course you can, but it won't be pretty
>> and wou would waste too much time.
>
> Might be you mix something up here ... it is simple algorithm.

No, its my fault, I didn't check and in my small math 'forfun'
library I used recursion.

>
>> Of course, if you see something like factorial, you shouldn't event
>> think and write it as a loop. But in other case, wasting time on
>> rewriting algorithm as a loop I consider premature optimalization.
>
> Depends how large factorials and how often are really need.
> Calculating 10,000,000! naively will take minutes and there are
> ways to optimize that:
> http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf

Interesting sport. I like it ;-)


> Sorry it is lisp, but the major number crunchers tend to love lisp.

)))))))))))))))

If you work with number theory you have to have enough
"RAM" in brain to track all brackets without effort :)

bartekltg

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

What practice can get speed improvement in C++? fl <rxjwg98@gmail.com> - 2015-07-14 16:53 -0700
  Re: What practice can get speed improvement in C++? Barry Schwarz <schwarzb@dqel.com> - 2015-07-14 17:23 -0700
    Re: What practice can get speed improvement in C++? bartekltg <bartekltg@gmail.com> - 2015-07-15 15:10 +0200
      Re: What practice can get speed improvement in C++? JiiPee <no@notvalid.com> - 2015-07-16 05:00 +0100
        Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-07-16 01:04 -0700
          Re: What practice can get speed improvement in C++? JiiPee <no@notvalid.com> - 2015-07-16 16:48 +0100
            Re: What practice can get speed improvement in C++? JiiPee <no@notvalid.com> - 2015-07-16 16:52 +0100
        Re: What practice can get speed improvement in C++? bartekltg <bartekltg@gmail.com> - 2015-07-16 13:23 +0200
          Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-07-16 06:54 -0700
            Re: What practice can get speed improvement in C++? bartekltg <bartekltg@gmail.com> - 2015-07-16 17:30 +0200
              Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-07-16 11:16 -0700
                Re: What practice can get speed improvement in C++? bartekltg <bartekltg@gmail.com> - 2015-07-17 17:06 +0200
          Re: What practice can get speed improvement in C++? JiiPee <no@notvalid.com> - 2015-08-04 16:14 +0100
  Re: What practice can get speed improvement in C++? Victor Bazarov <v.bazarov@comcast.invalid> - 2015-07-14 20:29 -0400
    Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-07-14 19:50 -0700
  Re: What practice can get speed improvement in C++? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2015-07-15 05:07 +0200
  Re: What practice can get speed improvement in C++? Lőrinczy Zsigmond <nospam@for.me> - 2015-07-15 06:38 +0200
  Re: What practice can get speed improvement in C++? Paavo Helde <myfirstname@osa.pri.ee> - 2015-07-15 00:22 -0500
    Re: What practice can get speed improvement in C++? fl <rxjwg98@gmail.com> - 2015-07-16 04:34 -0700
      Re: What practice can get speed improvement in C++? Martijn van Buul <pino@dohd.org> - 2015-07-21 09:28 +0000
  Re: What practice can get speed improvement in C++? Juha Nieminen <nospam@thanks.invalid> - 2015-08-03 08:16 +0000
    Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-03 13:48 -0700
      Re: What practice can get speed improvement in C++? Juha Nieminen <nospam@thanks.invalid> - 2015-08-04 08:21 +0000
        Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-08-04 08:07 -0700
        Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-04 10:15 -0700
          Re: What practice can get speed improvement in C++? Bo Persson <bop@gmb.dk> - 2015-08-04 20:09 +0200
            Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-04 12:38 -0700
              Re: What practice can get speed improvement in C++? Bo Persson <bop@gmb.dk> - 2015-08-05 17:03 +0200
                Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-05 23:32 -0700
            Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-08-05 03:55 -0700
          Re: What practice can get speed improvement in C++? Christopher Pisz <nospam@notanaddress.com> - 2015-08-04 14:09 -0500
            Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-04 12:18 -0700
              Re: What practice can get speed improvement in C++? Christopher Pisz <nospam@notanaddress.com> - 2015-08-04 14:50 -0500
              Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-08-05 04:11 -0700
          Re: What practice can get speed improvement in C++? Juha Nieminen <nospam@thanks.invalid> - 2015-08-05 08:12 +0000
            Re: What practice can get speed improvement in C++? Martin Shobe <martin.shobe@yahoo.com> - 2015-08-05 08:53 -0500
            Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-05 22:24 -0700
              Re: What practice can get speed improvement in C++? Ian Collins <ian-news@hotmail.com> - 2015-08-06 17:42 +1200
                Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-05 22:53 -0700
                Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-08-06 00:20 -0700
                Re: What practice can get speed improvement in C++? Christopher Pisz <nospam@notanaddress.com> - 2015-08-06 10:10 -0500
                Re: What practice can get speed improvement in C++? Bo Persson <bop@gmb.dk> - 2015-08-06 17:29 +0200
                Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-06 09:38 -0700
              Re: What practice can get speed improvement in C++? Juha Nieminen <nospam@thanks.invalid> - 2015-08-10 08:25 +0000
  Re: What practice can get speed improvement in C++? pip010 <pip010@gmail.com> - 2015-08-03 04:22 -0700

csiph-web