Anybody willing to decipher Forth program
in [Lisp]
|
From: Slobodan Blazeski on 10 Mar 2010 17:11 On Mar 10, 10:17 pm, Hugh Aguilar <hughaguila...(a)yahoo.com> wrote: > On Mar 9, 11:53 pm, Paul Donnelly <paul-donne...(a)sbcglobal.net> wrote: > > > Hugh Aguilar <hughaguila...(a)yahoo.com> writes: > > > I wrote a program to crack a linear-congruential encryption system in > > > both Factor and Forth and obtained these times on my laptop: > > > assembly-language 17 seconds > > > SwiftForth 22 seconds > > > Factor 9 minutes 14 seconds > > > I expect that Common Lisp would be even worse than Factor, although I > > > haven't tried it yet. > > > Why do you expect that? CL compilers are several decades more mature > > than Factor's compiler. > > I shouldn't have said that I expected Common Lisp to be worse than > Factor, as I had no reason to believe that. If a language doesn't > support mixed-precision integer arithmetic however, then I would > expect it to be worse than Forth --- and I've never heard of any > language other than Forth providing this feature. Factor has a variety > of different number types including rationals, and it can cast between > these as necessary, but this is still not mixed-precision arithmetic. > For mixed-precision, you have to be able to multiply two single- > precision integers to produce a double-precision product. Slava did > tell me that he was disturbed by the poor showing of Factor in regard > to LC53 and that he would upgrade the compiler to handle integer > arithmetic better. This was some time ago, so Factor may now be able > to do better than I have described above. > > The LC53 program is very short and simple. I would be interested in > seeing a port of LC53 into Common Lisp for speed comparison purposes. > I can describe the program here if anybody is interested: > > In the linear-congruential prng, the high bits have more influence > than the low bits, so I start guessing at the high bit and work down > to the low bit. I try setting the bit at 1 and 0, and I run HOW-FAR > for each guess. HOW-FAR uses this guessed key to calculate as far as > possible, and it stops when it either decrypts the entire message or > it begins generating a crypt-stream that doesn't match the known > plaintext. If it decrypts the entire message, then we are done and > have found our key. Otherwise we compare the two HOW-FAR calls to > determine whether the 1 or 0 bit went further. We then set this bit to > 1 or 0 and recursively try again with the next highest bit. If this > doesn't result in finding the seed, we toggle the bit and try again. > If HOW-FAR always told us the correct path to take, we could crack a > 32-bit key with only 32 tests. In practice, most of our early calls to > HOW-FAR result in the same value (zero), in which case we have to > arbitrarily choose to test the 1 or 0 first. A lot of these choices > are wrong, so our search is a dead-end. We are still much better off > than just doing a brute-force search though. A brute-force search > would find the key after testing about 50% of the total number of > keys. My algorithm is somewhere around 10%. > > The problem with my algorithm is that HOW-FAR often returns equal > values for the 1 and 0 guesses, in which case I have to arbitrarily > choose which guess to try first. An improvement would be that, if HOW- > FAR returns equal values, I would do a partial recursive search of > each guess to determine which side looks more promising. That would be > better than committing myself to a full recursive search of one side > of the tree based upon an arbitrary decision. I could do partial > recursive searches to give myself a more informed decision as to which > side is better, and then do a deeper recursive search of that side, > and so forth. For this to be efficient, I would have to save the > results of the partial recursive search on each side so that I don't > repeat that work when I do a deeper recursive search of whichever side > seems better. Lazy evaluation would be perfect for this. I would > pretend to have a full search of the every possible key, but would > fill-in the values of this search gradually as I did my partial > recursive searches. When I do deeper searches, I wouldn't have to redo > the work, but would just fetch the values that were set previously by > the partial search. If I were to upgrade the program from a 32-bit key > to a 64-bit key, I would have to also upgrade the program to do these > partial searches. This would pretty much require porting to a language > that supports lazy evaluation, as that would greatly simplify saving > that data. I'm really interested to see this code in lisp so if anybody who knows Forth (or maybe Factor) could decipher it in lisp or pseudo lisp would be grateful : http://paste.lisp.org/display/96222 thanks Slobodan
From: Hugh Aguilar on 10 Mar 2010 17:24 On Mar 10, 3:11 pm, Slobodan Blazeski <slobodan.blaze...(a)gmail.com> wrote: > On Mar 10, 10:17 pm, Hugh Aguilar <hughaguila...(a)yahoo.com> wrote: > > The LC53 program is very short and simple. I would be interested in > > seeing a port of LC53 into Common Lisp for speed comparison purposes. > > I can describe the program here if anybody is interested: > > ... > > I'm really interested to see this code in lisp so if anybody who knows > Forth (or maybe Factor) could decipher it in lisp or pseudo lisp would > be grateful :http://paste.lisp.org/display/96222 For both symtab.4th and LC53.4th I have Factor versions that are exact ports. The novice package on FIG's website only contains the Forth versions though. If anybody wants to see a Factor (or assembly) version, let me know and I will either email it to you or post it somewhere that you can download it. Maybe one of my first Lisp projects will be to port one of these short programs --- and only later tackle the slide-rule program which is quite large.
From: Slobodan Blazeski on 10 Mar 2010 17:36 On Mar 10, 11:24 pm, Hugh Aguilar <hughaguila...(a)yahoo.com> wrote: > On Mar 10, 3:11 pm, Slobodan Blazeski <slobodan.blaze...(a)gmail.com> > wrote: > > > On Mar 10, 10:17 pm, Hugh Aguilar <hughaguila...(a)yahoo.com> wrote: > > > The LC53 program is very short and simple. I would be interested in > > > seeing a port of LC53 into Common Lisp for speed comparison purposes. > > > I can describe the program here if anybody is interested: > > > ... > > > I'm really interested to see this code in lisp so if anybody who knows > > Forth (or maybe Factor) could decipher it in lisp or pseudo lisp would > > be grateful :http://paste.lisp.org/display/96222 > > For both symtab.4th and LC53.4th I have Factor versions that are exact > ports. The novice package on FIG's website only contains the Forth > versions though. If anybody wants to see a Factor (or assembly) > version, let me know and I will either email it to you or post it > somewhere that you can download it. > > Maybe one of my first Lisp projects will be to port one of these short > programs --- and only later tackle the slide-rule program which is > quite large. If you could rewrite it in lisp or some sort of pseudo lisp it could be quickly improved and allow you to make comparisons. Slobodan
From: Helmut Eller on 11 Mar 2010 04:27 * Slobodan Blazeski [2010-03-10 23:11+0100] writes: > I'm really interested to see this code in lisp so if anybody who knows > Forth (or maybe Factor) could decipher it in lisp or pseudo lisp would > be grateful : > http://paste.lisp.org/display/96222 Below is a naive translation to Lisp. You need to create a file test.txt with the string to be tested. I haven't found that in the novice.zip package. I guess this is the kind of program were Lisp spends most of the time boxing/unboxing/garbage collecting integers. Helmut
From: Nicolas Neuss on 11 Mar 2010 05:02
Helmut Eller <eller.helmut(a)gmail.com> writes: > * Slobodan Blazeski [2010-03-10 23:11+0100] writes: > >> I'm really interested to see this code in lisp so if anybody who knows >> Forth (or maybe Factor) could decipher it in lisp or pseudo lisp would >> be grateful : >> http://paste.lisp.org/display/96222 > > Below is a naive translation to Lisp. Wonderful! > You need to create a file test.txt with the string to be tested. I > haven't found that in the novice.zip package. Hugh? > I guess this is the kind of program were Lisp spends most of the time > boxing/unboxing/garbage collecting integers. This would mean that it probably can be accelerated a lot on many CL implementations by inserting a little bit of type information. But before starting premature optimization we should really have "test.txt" so that we can compare the output and the CPU time with what was written before: > > assembly-language 17 seconds > > SwiftForth 22 seconds > > Factor 9 minutes 14 seconds Nicolas |