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

Groups > comp.lang.c > #128196

Re: Copy array with small changes

From Noob <root@127.0.0.1>
Newsgroups comp.lang.c
Subject Re: Copy array with small changes
Date 2018-03-22 17:10 +0100
Organization A noiseless patient Spider
Message-ID <p90ki0$8f8$1@dont-email.me> (permalink)
References (1 earlier) <slrnpac9bc.eu5.grahn+nntp@frailea.sa.invalid> <p864ci$btf$1@dont-email.me> <87sh95ur60.fsf@bsb.me.uk> <p86v82$r6q$1@dont-email.me> <kfnin9ups0d.fsf@x-alumni2.alumni.caltech.edu>

Show all headers | View raw

On 17/03/2018 17:48, Tim Rentsch wrote:

> Noob writes:
> 
>> The task is to evaluate all arithmetic expressions involving
>> N numbers and the 4 arithmetic operators [+ - * /]
>>
>> There's a combinatorial explosion as N grows, the number of
>> expressions to evaluate grows out of reach:
>>
>> For N=7, ~4e7  evals
>> For N=8, ~5e9  evals
>> For N=9, ~6e11 evals
>> For N=10, 1e14 evals (extrapolated, didn't run it)
> 
> Either I'm not understanding you, or something is off in these
> numbers.  If N is 2, there are 6 possibilities - one for each of
> the four operations, plus one more for each of the two asymmetric
> ones.  If N is 3, there are 3*6*6, or 108.  And so forth.  This
> gives a much larger value for N=7, about 2e9.  What am I missing?

You're right in theory :-)

Let 'E' be the number of expressions to evaluate.

E = PROD{i=2..n}(4*C(2,i))

However, in most cases, the division is not possible
(remainder is non-zero), x*1 and y/1 are not evaluated,
a-b=0 is ignored.

In practice, the number of expressions to evaluate comes
out smaller than what theory "predicts".

I'll post my code next week for people to suggest improvements.

Regards.

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

Thread

Copy array with small changes Noob <root@127.0.0.1> - 2018-03-11 22:51 +0100
  Re: Copy array with small changes supercat@casperkitty.com - 2018-03-11 15:11 -0700
  Re: Copy array with small changes Richard Damon <Richard@Damon-Family.org> - 2018-03-11 18:12 -0400
    Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-11 22:35 +0000
      Re: Copy array with small changes Richard Damon <Richard@Damon-Family.org> - 2018-03-13 13:10 -0400
  Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-11 22:13 +0000
    Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 00:04 +0000
    Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 10:35 +0000
      Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 12:37 +0000
        Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 13:10 +0000
        Re: Copy array with small changes Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-03-12 13:34 +0000
          Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:22 -0700
        Re: Copy array with small changes mark.bluemel@gmail.com - 2018-03-12 07:47 -0700
          Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 14:56 +0000
            Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 15:14 +0000
            Re: Copy array with small changes mark.bluemel@gmail.com - 2018-03-12 08:53 -0700
        Re: Copy array with small changes Keith Thompson <kst-u@mib.org> - 2018-03-12 09:08 -0700
          Re: Copy array with small changes supercat@casperkitty.com - 2018-03-12 09:57 -0700
            Re: Copy array with small changes Richard Damon <Richard@Damon-Family.org> - 2018-03-13 13:21 -0400
    Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-12 15:25 +0100
      Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 15:09 +0000
  Re: Copy array with small changes Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-03-12 06:59 +0000
    Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-12 15:55 +0100
      Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 15:07 +0000
      Re: Copy array with small changes mark.bluemel@gmail.com - 2018-03-12 09:03 -0700
      Re: Copy array with small changes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-03-12 17:42 +0000
        Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-12 23:33 +0100
          Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-12 23:44 +0100
          Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:48 -0700
            Re: Copy array with small changes Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-18 03:31 -0700
            Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-22 17:10 +0100
        Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:24 -0700
          Re: Copy array with small changes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-03-17 18:04 +0000
            Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-26 22:55 -0700
              Re: Copy array with small changes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-03-27 15:28 +0100
                Re: Copy array with small changes Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-28 14:42 -0700
      Re: Copy array with small changes Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-03-13 12:46 +0000
  Re: Copy array with small changes Anton Shepelev <anton.txt@gmail.com> - 2018-03-12 22:36 +0300
  Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-12 23:32 +0100
    Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-13 10:42 +0100
    Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-13 11:37 +0100
      Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-13 21:27 +0100
  Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:55 -0700

csiph-web