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

Groups > comp.programming > #8259

Re: Looking for simple brute force solution

Show all headers | View raw

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> 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.

The outer loop is to count from 0 to 3^N. The inner loop is to
work the outer loop counter down to 0 via a sequence of /3
operations. Within the inner loop I have to keep track of how
many times I have done the /3 operation because that determines
which number in the table I am currently using.

>
>
> 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.

No, the inner loop is only dealing with the loop index of the outer
loop. The depth of the inner loop is the number of base 3 digits
it takes to express the outer loop index.

>
>
> 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.
>

I agree it's not looking good.

I really appreciate your insight and I have to add your idea to my bag
of programming tricks. It can easily be expanded to allow any number
of options for items in the list.

Thanks again.

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