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

Groups > comp.programming > #8255

Re: Looking for simple brute force solution

Show all headers | View raw

root <NoEMail@home.org> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> root <NoEMail@home.org> writes:
>><snip>
>>
>> You can just count up to 3^N.  Call the count i.  For each number in the
>> set you use i%3 to determine if you add, subtract or ignore.  For the
>> next number you set i = i/3 and repeat.  In effect you are pulling out
>> the base-3 digits of i.  (I'm using % to mean remainder and / for
>> integer division.)
>
> Yes, that is the solution I was looking for. Thanks.
>
> I can do that with two nested loops instead of N.

OK, but I don't see why you need two nested loops.  That's bad news
because you are squaring an already exponential function.

>> That's a lot of sums to calculate.  If you can do a million a second,
>> N=30 would take over 6.6 years.  N=20 is more manageable but even then I
>> think you might have to take some shortcuts.
>
> On my machine a real case of N=12 took no noticeable time so I think that
> I could easily handle N=15.  N=20 would be about 6,000 times as long,
> but I could let the machine crank away over night.

2^20 is 6,561 times 2^12, but if you have two 'N' nested loops, that
would be 6,561 * 6,561 = 43,046,721 times longer.

> The actual data are not very encouraging: there are 30 entries leading
> up to the determination of operating income, and another 22 to reach
> net income. The entries in the income statement do not conform to
> any accounting standard familiar to me.

It's not looking good.  You may need to find some good-enough answers,
or hope that the data are such that whole swathes of the search can be
eliminated.

-- 
Ben.

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

Thread

Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-03 23:18 +0000
  Re: Looking for simple brute force solution fir <profesor.fir@gmail.com> - 2018-01-03 16:49 -0800
    Re: Looking for simple brute force solution fir <profesor.fir@gmail.com> - 2018-01-03 17:11 -0800
      Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 10:14 +0000
        Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 10:52 -0500
          Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 16:46 +0000
            Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 12:37 -0500
  Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-03 21:28 -0500
    Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 09:42 +0000
      Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 10:16 -0500
        Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 17:26 +0000
          Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 21:19 +0000
  Re: Looking for simple brute force solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-04 02:29 +0000
    Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 09:55 +0000
      Re: Looking for simple brute force solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-04 14:29 +0000
        Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 16:55 +0000
          Re: Looking for simple brute force solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-04 20:36 +0000
      Re: Looking for simple brute force solution Robert Wessel <robertwessel2@yahoo.com> - 2018-01-04 12:03 -0600
        Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 21:28 +0000
          Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 21:50 +0000
            Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 23:06 +0000
            Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 21:35 -0500
              Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-05 05:59 +0000
                Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-05 16:48 +0000
                Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-06 08:50 -0500
                Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-06 16:47 +0000

csiph-web