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=-0.4 required=5.0 tests=AC_FROM_MANY_DOTS,BAYES_00 autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,c42dbf68f5320193 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-05-09 06:38:20 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!sn-xit-06!supernews.com!news-x2.support.nl!psinet-eu-nl!psiuk-p4!uknet!psiuk-p3!uknet!psiuk-n!news.pace.co.uk!nh.pace.co.uk!not-for-mail From: "Marin David Condic" Newsgroups: comp.lang.ada Subject: Re: Generation of permutations Date: Wed, 8 May 2002 10:10:43 -0400 Organization: Posted on a server owned by Pace Micro Technology plc Message-ID: References: NNTP-Posting-Host: dhcp-200-133.miami.pace.co.uk X-Trace: nh.pace.co.uk 1020867046 8451 136.170.200.133 (8 May 2002 14:10:46 GMT) X-Complaints-To: newsmaster@news.cam.pace.co.uk NNTP-Posting-Date: 8 May 2002 14:10:46 GMT X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 Xref: archiver1.google.com comp.lang.ada:23760 Date: 2002-05-08T14:10:46+00:00 List-Id: wrote in message news:qD2C8.41$k97.25193567@newssvr13.news.prodigy.com... > As Dewar points out, you just keep snapshots of all the states the > program has gone through and check for "Hey! We've been here before!". > Your RAM + disk have a finite number of bits N so there are at most 2**N > possible states it can wander among. If the instruction execution time is > t, it can't run more than t*2**N without repeating itself. I *think* I follow - but that seems to disallow any sort of looping. (Or do I misunderstand?) Isn't it possible for a program to be in a state it has been in before (iterating through the data on disk again...) and not be caught in an infininte loop? Or because you're including a check of the state of the data as well, then it can't be in the same state plus the identical state of the data without being caught in a loop? (So if you had 1k of program+data+processor_state, you'd save every bit, execute one clock cycle, compare the 1k against every previous 1k and if it matches, its stuck and throw it out? Sounds deliciously slow! :-) Or you can > calculate how long T some standard sort algorithm would take, maximum, > then abort if your randomly generated program is still running at T+1 sec. But that's just looking for the occurrence of a specific algorithm, isn't it? Say I calculate the time needed for the Slow Sort algorithm (permutations) to get through some data and use this as the worst case. I'd reject every valid random algorithm that was T>Slow Sort. I'm sure I can come up with valid code that sorts at a time greater than that of the Slow Sort (Slow Sort plus delay (1.0), if nothing else.) So really, you're saying "I want to see how long it takes to randomly generate at least the Slow Sort algorithm." I can see that this works, but it seems sub-optimal. :-) It might make a great article & example of tasking (One task sets the other task to its sorting job & monitors the time, shooting it in the head & restarting it as needed...) to implement something like this. :-) MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com