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

Groups > comp.lang.c > #18013

Re: Which operation is more expensive?(a <= b and a != 0)

Show all headers | View raw

On 2012-02-27, Ping Cheu <nospam@nospam.com> wrote:
> From a web-site that teaches optimization for c,
>
> I saw bellow optimization rule.
>
>     int fact1_func (int n)
>     {
>         int i, fact = 1;
>         for (i = 1; i <= n; i++)
>           fact *= i;
>         return(fact);
>     }

Your function will invoke multiplication overflow (undefined behavior) for
values of n which are not that large.

>     int fact2_func(int n)
>     {
>         int i, fact = 1;
>         for (i = n; i != 0; i--)
>            fact *= i;
>         return(fact);
>     }
>
> The author say 'fact2_func' is faster than 'fact1_func'.

Worrying about this is pointless because the factorial function grows so fast
relative to the constrained range of int, that you cannot have a significantly
large domain value of n.

This also means it is practical to do it with a table lookup:

  int fact3_func(int n)
  {
    /* This table is going to be quite small: */
    static int fact_table[] = { 1, 1, 2, 24, 120, ...}

    if (n >= 0 && n < sizeof fact_table / sizeof *fact_table)
      return fact_table[n];

    /* trouble: what to do? */
    return -1;
  }

Before you worry about how the direction of the loop affects machine
cycles, consider the limiting circumstances and the algorithm.

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

Thread

Which operation is more expensive?(a <= b and a != 0) Ping Cheu <nospam@nospam.com> - 2012-02-27 21:24 +0000
  Re: Which operation is more expensive?(a <= b and a != 0) James Kuyper <jameskuyper@verizon.net> - 2012-02-27 16:47 -0500
    Re: Which operation is more expensive?(a <= b and a != 0) Michael Angelo Ravera <maravera@prodigy.net> - 2012-03-07 04:23 -0800
  Re: Which operation is more expensive?(a <= b and a != 0) Keith Thompson <kst-u@mib.org> - 2012-02-27 13:54 -0800
    Re: Which operation is more expensive?(a <= b and a != 0) falk@rahul.net (Edward A. Falk) - 2012-02-27 23:47 +0000
  Re: Which operation is more expensive?(a <= b and a != 0) Shao Miller <sha0.miller@gmail.com> - 2012-02-27 16:57 -0500
    Re: Which operation is more expensive?(a <= b and a != 0) Stephen Sprunk <stephen@sprunk.org> - 2012-02-28 13:43 -0600
  Re: Which operation is more expensive?(a <= b and a != 0) Richard Damon <news.x.richarddamon@xoxy.net> - 2012-02-27 16:58 -0500
  Re: Which operation is more expensive?(a <= b and a != 0) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-02-27 13:55 -0800
    Re: Which operation is more expensive?(a <= b and a != 0) Kenneth Brody <kenbrody@spamcop.net> - 2012-03-03 15:58 -0500
  Re: Which operation is more expensive?(a <= b and a != 0) Keith Thompson <kst-u@mib.org> - 2012-02-27 14:17 -0800
  Re: Which operation is more expensive?(a <= b and a != 0) Barry Schwarz <schwarz45@yahoo.com> - 2012-02-27 14:52 -0800
    Re: Which operation is more expensive?(a <= b and a != 0) Peter Nilsson <airia@acay.com.au> - 2012-02-27 18:16 -0800
      Re: Which operation is more expensive?(a <= b and a != 0) qarnos <darrencubitt@gmail.com> - 2012-02-29 12:20 -0800
      Re: Which operation is more expensive?(a <= b and a != 0) Barry Schwarz <schwarzb@dqel.com> - 2012-03-13 22:07 -0700
  Re: Which operation is more expensive?(a <= b and a != 0) Kaz Kylheku <kaz@kylheku.com> - 2012-02-28 00:56 +0000
  Re: Which operation is more expensive?(a <= b and a != 0) Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2012-02-27 19:18 -0700
    Re: Which operation is more expensive?(a <= b and a != 0) China Blue Sea <chine.bleu@yahoo.com> - 2012-02-27 18:30 -0800
  Re: Which operation is more expensive?(a <= b and a != 0) "BartC" <bc@freeuk.com> - 2012-02-28 13:22 +0000
  Re: Which operation is more expensive?(a <= b and a != 0) Stephen Sprunk <stephen@sprunk.org> - 2012-02-28 13:38 -0600
  Re: Which operation is more expensive?(a <= b and a != 0) jgk@panix.com (Joe keane) - 2012-02-28 22:35 +0000
    Re: Which operation is more expensive?(a <= b and a != 0) Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-03-03 01:36 +0200
      Re: Which operation is more expensive?(a <= b and a != 0) jgk@panix.com (Joe keane) - 2012-03-05 20:03 +0000
        Re: Which operation is more expensive?(a <= b and a != 0) Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-03-12 01:08 +0200
          Re: Which operation is more expensive?(a <= b and a != 0) Harald van Dijk <haraldvdijk@gmail.com> - 2012-03-12 00:05 -0700
            Re: Which operation is more expensive?(a <= b and a != 0) James Kuyper <jameskuyper@verizon.net> - 2012-03-12 08:59 -0400
              Re: Which operation is more expensive?(a <= b and a != 0) gwowen <gwowen@gmail.com> - 2012-03-12 06:24 -0700
                Re: Which operation is more expensive?(a <= b and a != 0) James Kuyper <jameskuyper@verizon.net> - 2012-03-12 10:13 -0400
                Re: Which operation is more expensive?(a <= b and a != 0) Keith Thompson <kst-u@mib.org> - 2012-03-12 10:44 -0700
                Re: Which operation is more expensive?(a <= b and a != 0) Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-03-13 17:12 +0200
          Re: Which operation is more expensive?(a <= b and a != 0) Keith Thompson <kst-u@mib.org> - 2012-03-12 11:20 -0700

csiph-web