Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: gah4 Newsgroups: comp.compilers Subject: Re: binary search debugging of compilers Date: Sun, 14 May 2023 13:38:36 -0700 (PDT) Organization: Compilers Central Sender: johnl@iecc.com Approved: comp.compilers@iecc.com Message-ID: <23-05-008@comp.compilers> References: <23-05-003@comp.compilers> <23-05-005@comp.compilers> <23-05-006@comp.compilers> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="85337"; mail-complaints-to="abuse@iecc.com" Keywords: debug, tools Posted-Date: 14 May 2023 22:42:20 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com In-Reply-To: <23-05-006@comp.compilers> Xref: csiph.com comp.compilers:3464 On Sunday, May 14, 2023 at 9:20:54 AM UTC-7, Kaz Kylheku wrote: (snip) > Setup: > > We can (somehow) enumerate the N entities with integers, which we > express using a pure binary enumeration. Then, we can discover the > number of an erroneously processed element, one bit at a time. > > Procedure: > > First we treat all elements numbered ..XXXXXX0 using the new technique > technique, and all others using the the old technique. If the > system fails, we know that it's the ..XXXXX0 set which has one or more > badly processed elements. Otherwise it's the other set, whose > enumerations end in a 1. Either way, we have discovered the identity of > the last bit. There is the assumtion that only one of the N is in error. Reminds me of ECC memory, which can correct one bit errors, and detect two bit errors. After log(N) tests, you find the one that it is supposed to be, fix it, and it either works or doesn't. Then you work on a new set of tests. Or start out with a more complicated set, which can learn more in one set.