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

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

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

Show all headers | View raw

On 16.07.2015 15:54, Öö Tiib wrote:
> On Thursday, 16 July 2015 14:23:56 UTC+3, bartekltg  wrote:
>> On 16.07.2015 06:00, JiiPee wrote:
>>> On 15/07/2015 14:10, bartekltg wrote:
>>>> On 15.07.2015 02:23, Barry Schwarz wrote:
>>>>
>>>>
>>>>
>>>>>
>>>>>> What is your opinion to the question?
>>>>>
>>>>> The best way of improving speed is to select or design a speed
>>>>> efficient algorithm.  For a trivial example, computing factorials will
>>>>> be faster in a loop than using recursion.
>>>>
>>>> IMHO it shoud be threated as the same algorithm, just different
>>>> execution. I think changing recursion to loops, aside from
>>>> oblivious cases like factorial, is premature optimalization.
>>>> And in simple cases it change nothing, compiler will change
>>>> it for us:
>>>>
>>>> c++ code:
>>>> int factorial (int x){
>>>>      if (x>1)  return x*factorial(x-1);
>>>>      else return x;
>>>> }
>>>
>>> factorial maybe not the best example as I would do it using constexpr:
>>> constexpr long long fac(int k)
>>> {
>>>       return (k == 0) ? 1 : k * fac(k - 1);
>>> }
>>> giving an instant answer (calculated compile time).
>>
>> Sure...
>>
>> main(){
>> 	big_int x;
>> 	cin>>c;
>> 	cout<<fac(x);
>> }
>>
>> ;-)
>
> My psychic abilities fail me ... what is here 'big_int' and what is 'c'

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.

 > and is the 'fac' here called with uninitialized argument?

Sorry, a typo, should be
	cin>>x;

The point is, constexpr will help us when... the argument is constant;-)
In the other case, it is just a function.


>
>> Also, instead int we have for example arthmetic modulo 1 178 973 853,
>> so x can be too bit to put every possible answer in a array.
>
> Who suggested to put answers to array?In both functions


I just skip two post:

I: constexpr cant help with nonconst.
somebody: you can put answers in a small array, small because
21! is outside range of uint64_t.
I: for factorial yes, but not always. Look at modified problem 
(factorial modulo).

 > all checks are missing but neither puts anything to array.

It doesn't matter, computing "factorial of integer munbers in modulo
arithmetic" is quite artificial problem. This is only a simple example.

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? I think of course you can, but it won't be pretty
and wou would waste too much time.

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.

Of course, there is always an exception. For GPU you probably start
from removing all recursions ;-)

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