From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: 103376,9dfc10efb95ba130
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news1.google.com!news3.google.com!feeder.news-service.com!newsfeed.straub-nv.de!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: Ludovic Brenta <ludovic@ludovic-brenta.org>
Newsgroups: comp.lang.ada
Subject: Re: Inefficient algorithms
Date: Sat, 11 Sep 2010 11:23:04 +0200
Organization: A noiseless patient Spider
Message-ID: <87hbhwab2f.fsf@ludovic-brenta.org>
References: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
	<8f0nd6F8ucU1@mid.individual.net> <8f0o4uFct8U1@mid.individual.net>
	<87lj78ab6m.fsf@ludovic-brenta.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sat, 11 Sep 2010 09:23:04 +0000 (UTC)
Injection-Info: mx01.eternal-september.org;
 posting-host="Tx8o3nVba1W9I4g5qQx/8Q";
	logging-data="9218"; mail-complaints-to="abuse@eternal-september.org";
	posting-account="U2FsdGVkX19bG1KGQH/ZoQC2nvPAkozz"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux)
Cancel-Lock: sha1:K5A7MpQgMhMezmkVkADE0LfqMjo=
	sha1:yym92sOyWz4Z2ww4jDllj+fHVK8=
Xref: g2news1.google.com comp.lang.ada:14012
Date: 2010-09-11T11:23:04+02:00
List-Id: <comp.lang.ada>

I just wrote on comp.lang.ada:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>> Niklas Holsti wrote:
>>> Rick wrote:
>>>> I am working on a class in algorithmic efficiency and, to make a
>>>> point, need an algorithm that runs O(2^n) - a factoring algorithm
>>>> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
>>>> please help with an Ada example.
>>>
>>> Perhaps the canonical example is this: you are given a Boolean
>>> formula containing n Boolean variables. Find a valuation (a value,
>>> True or False, for each variable) that makes the formula True.
>>
>> Replying to myself, since I realize that I probably misunderstood your
>> need: what you want is an inefficient O(2^n) solution to an easy
>> (non-exponential) problem. The problem I suggested is not, of course,
>> an easy one. But it has easy variants. For example, require that the
>> Boolean formula uses at most 10 of the n variables, where this limit
>> (10) is considered a fixed number independent of the total number (n)
>> of variables.
>
> Actually I do think that the problem is trivial and that you can solve
> it without recursion.  If you see your array of Booleans as a number in
> binary representation:
>
> procedure Inefficient (N : in Natural) is
>
>    subtype Valuation is Natural range 1 .. 2**N;

Make that 0 .. 2**N, of course.

>    -- We assume the solution is Valuation'Last but it could be any value.
>    Solution : constant Valuation := Valuation'Last;
> begin
>    for K in Valuation'Range loop
>       exit when K = Solution;
>    end loop;
> end Inefficient;

Granted, a decent optimizing compiler might grab victory from the jaws
of defeat in this case :)

-- 
Ludovic Brenta.