pmcgee

I have been learning about RSA encryption/decryption, so I started getting to know the (Rudy Velthuis') BigNumbers project, via GetIt and D12.3. I started running into frustrating overflow errors (EIntOverflow) as soon as I started generating large prime numbers and doing some arithmetic with them. I ended up trying the original Github repo (https://github.com/rvelthuis/DelphiBigNumbers) and using 10.3.3, and it worked fine. Since then I spent quite some time to pull apart a simple line like: const C CMultiplier = UInt64(6364136223846793005); CIncrement = UInt64(1442695040888963407); begin {$IFOPT Q+} {$DEFINE HasRangeChecks} {$ENDIF} FSeed := Int64(FSeed * CMultiplier + CIncrement); // << EIntOverflow Result:= UInt32(FSeed shr (64 - Bits)); // Use the highest bits; Lower bits have lower period. {$IFDEF HasRangeChecks} {$RANGECHECKS ON} {$ENDIF} end; Eventually, as a diagnostic adventure, I turned the one line into a soup of smaller steps to avoid overflow, and it works: // (A.e32 + B) * (C.e32 + D) = AC.e64 + (AD+BC).e32 + BD A := FSeed shr 32; // top 32 bits C := CMultiplier shr 32; B := FSeed and $ffffffff; // bottom 32 bits D := CMultiplier and $ffffffff; BD := B*D; ADBC := A*D+B*C; //F := ( (ADBC shl 32) + BD + CIncrement ); f1 := BD + CIncrement; f2 := ADBC shl 32; F := (f1 and $0fffffffffffffff) + (f2 and $0fffffffffffffff); FSeed := Int64(F); //FSeed := Int64(FSeed * CMultiplier + CIncrement); (This is inaccurate on the single most significant bit, but the algorithm says it's only using 48 bits, and has tested correctly so far) I haven't tried 10.4.2, but 11.3 and 12.3 both give the overflow error. Is this issue known to anyone?

The original Github repo (https://github.com/rvelthuis/DelphiBigNumbers) has a pdf by Rudy explaining the library. And it says this :

PS : I have submitted an update to the TurboPack repo on Github, with the appropriate attribution back to this thread. https://github.com/TurboPack/RudysBigNumbers/pull/10

Yes. Right. Got it. I did go to the link, but my brain saw the (az+b)(cz+d) and totally failed to see that this was exactly the z = 1.e32 (in binary) that I was using. And thank you for the information about the Elliptic Curve stuff (El-Gamal) to read up on. I'll be very interested to read it.

No, I don't think so. I was just doing the multiplication in pieces that didn't overflow 64 bits. I was just taking a multiplication of two 64-bit numbers, and thinking of it kinda like a long multiplication from school. If we consider each number in their two halves (upper and lower 32 bits), then when we only want to keep the bottom 64-bits, we can throw away part of the multiplications ... and do some of the multiplication in the lower part of the range before shifting it back up again. Yes. I was going to be potentially incorrect in the 64th bit, but it was easy to do, and wasn't affecting the testing I had done to that stage. No, not at all. I have been, with friends, going through Alexander Stepanov's book (and related videos) "From Mathematics to Generic Programming", and he describes RSA in there. We set ourselves the task to implement it in different languages. Its pretty remarkable how simple the mechanical parts are (in concept).

Thanks for your reply. These directives are just quoted as-is from the library on GitHub (uptodate and original) and GetIt. I haven't pulled back to get the higher level view here, having been stuck in tracing through the code to nail down the issues. FSeed is declared as Int64. The function here is : function TRandom.Next(Bits: Integer): UInt32; And the call is : Rnd := Next(32); where Rnd is declared as Integer; I have checked that the actual bits (of course, I guess) stay the same ... but this seemingly cavalier application of (kinda) hidden casting has caused me to squint a little. 🤨 Edit : Incorporating the corrected compiler directives, sanity is returned and FSeed can be calculated in one line again. 🎉 In procedure TRandomBase64.NextBytes(var Bytes: array of Byte); Rnd is declared as UInt64. With the above change, there is a Range Check Error on assigning Rnd (in TRandom.NextBytes) I think it is clear that Rnd should be declared as UInt32. Aaaaannnnd, on reading further down your response, I see you already concluded the same. 😅

{$APPTYPE CONSOLE} program Project1; uses System.SysUtils, System.generics.defaults; type TEmp = class FName : string; FSalary: Currency; FAcNo : integer; function Gett<T> (var field:T) : T; procedure Sett<T> (var field:T; const Value : T); end; function TEmp.Gett<T> (var field:T) : T; begin result := field; end; procedure Temp.Sett<T>(var field:T; const Value : T); begin var lComparer := TEqualityComparer<T>.Default; if lComparer.Equals(Value, Default(T)) then raise Exception.Create('Field must have a non-default value') else field := value; end; // credit to https://stackoverflow.com/questions/5344433/how-can-i-declare-a-pointer-based-on-a-generic-type // regarding Generic comparison to Default(T), and an idea of generic properties. var emp : TEmp; s : currency; a : integer; begin s := 1000.37; a := 123; emp := TEmp.Create; writeln('Name : ', emp.FName ); writeln('Salary : ', emp.FSalary:6:2 ); writeln('Ac # : ', emp.FAcNo ); writeln; emp.Sett(emp.FName, 'Abc Def'); emp.Sett(emp.FSalary, s); emp.Sett(emp.FAcNo, a); writeln('Name : ', emp.Gett(emp.FName) ); writeln('Salary : ', emp.FSalary:6:2 ); writeln('Ac # : ', emp.FAcNo ); readln; end. I was just playing around ... trying to figure out what a simple generic 'property' function could look like. Someone in 2009 had already been thinking down that track.

The Advent of Code 2024. ChatGPT >> I’d like to encourage lots of Delphi people to have a crack and maybe compare solutions - online or at a meeting. Each day is pretty much independent of the others … but the concepts might build upon previous days’ puzzles. Fun starts on 1st December. Link → The Advent of Code 2024

I'm 100% not an expert on DLLs ... but I know people have even used Delphi compiled Dlls with eg C# applications. (Maybe it would be best to imagine a D10 vs D12 as being incompatible to that sort of degree?)

Going off your picture ... I'd say 'Yes', I think you are over-complicating things. But it is normal for us to come at a problem, trying out various ideas ... getting too close to the problem, going down dead ends, and then finally making some realisations that simplify the whole thing. Sometimes over and over and over - until hopefully achieving a simple and elegant solution. Consider just making a StringList. {$APPTYPE CONSOLE} program Project1; uses System.Classes, System.Types; type TState = (int, alpha); const Digits : set of char = ['0','1','2','3','4','5','6','7','8','9']; function Parse( s:String ) : TStringList; begin Result := TStringList.Create; var state : TState := int; var temp : string := ''; for var ch in s do case state of int: if ch in Digits then temp := temp+ch else begin if temp <> '' then result.Add(temp); temp := ch; state := alpha; end; alpha: if not (ch in Digits) then temp := temp+ch else begin if temp <> '' then result.Add(temp); temp := ch; state := int; end; end; if temp <> '' then result.Add(temp); end; begin var s:TStringList := Parse('12abcd345ghi6kl7mnopq890'); writeln( s.Text ); s.Free; readln; end. (Actually, with a StringList, all you'd really have to do is insert your chosen delimiter between runs of Alphas and Ints. But I wanted to model a bit more general approach.)

There might be a marketing imperative, for new Delphi people (assuming there are some), to be able to immediately show zero-effort Windows programming, say bouncing a ball around a square ... with drag and drop components, and nice event-driven functionality. I think that addresses one market. However, I think as a programming enthusiast, coming to a new language like eg Swift, Haskell, Zig, or Odin .. or even C, C++, or Rust, then I want to understand the language itself and the expressions and idioms. Every time I am trying out new ideas (to me) in Delphi, or eg recently with the Advent of Code, I am writing a console program. I think it's the cleanest and simplest way. Sure there are certainly things, like events and messaging, that you will probably do with a gui program ... but yeah, I like the console.

The speed thing is addressed in the 'Behind the Scenes' video ... people who are the Olympic athletes at this event have entire solution systems pre-prepared for reading in and manipulating data, and then solving the puzzle. The head guy mentions that people will blast through, ignoring the text, maybe even guessing at the problem being asked in the quest for a fastest solution. He specifically says that that endeavour is not "programming" as such ... it's an entirely different beast.

Personally, I post everything that it takes to recreate my answer. And any sundry files (like Excel) I might employ to help along the way. Reproducible Research™ 🙂 Ha. I feel this pain. 😅 I have often found my code volume increasing like an expanding balloon ... until I have worked out what I should have been doing, then the cutting away begins ... and 80 lines drops back to 20. I have this currently in my solution for Problem 5 Part 2. 60 out of 120 lines became unnecessary as I realised the information I needed to gather ... but the exploration process was necessary to come to that understanding in the first place. 🙂

If you can see it on the screen, you can capture video of your screen. If it's in the IDE, then eg Delphi has a CodeInsight bar that buzzes up a little for a moderate size project (like DevCpp), loading or analyzing some stuff, then disappears.

I was following an idea that I had thought of yesterday ... and now have the form of the solution. I was assuming the data was less strictly complete than it is, so in reality it's not so hard actually.

I made a quick video of an (unsolved atm) part I liked of Q5-2 ...

@JohnLM ... (Throwing a possible small spanner) ... I'm not sure from the gif ... are you sorting the two lists?

One thing that is part of the challenge, from my perspective ... is when you can deal with Part 2 with only a reasonably small modification of your Part 1 solution. Maybe it's just me, but I find that very satisfying when it happens. 😎

I don't think you should be bothered about watermarks. In my favourite 'podcast with slides' of well over 100 episodes, the 'Activate Windows' logo has become an expected, even demanded, regular character.

@jesu I see this was a while back, but I'd encourage you to look up the idea of an Optional type. (One of) the points of an optional type, is that it doesn't reduce the value space of your inhabited type. Using 'NaN' or '-1' or whatever as a magic value might interfere with the validity of your use of the Double value. With an optional type , the inhabited type is uncontaminated by any other interpretation or usage. You can look at what it looks like in eg Spring4D, but here's the basic idea : type Maybe_Double = record // or Optional_Double ok : boolean; d : double; end; function Safe_Sqrt( i:integer ) : Maybe_Double; begin if i<0 then result.ok := false else begin result.ok := true; result.d := sqrt(i); end; end; begin for var i:= -2 to 2 do begin var ss := Safe_Sqrt(i); if ss.ok then writeln(i, ' ', d) else writeln(i, ' ','Undefined'); end; end. PS : Another feature of an optional type is that all uses of the inhabited type transfer into the "optional world". // If you have a function F( d:double ) : string, // then you can automatically have an 'identical' function OptF( od:maybe_double ) : maybe_string; begin if od.ok then exit( F(od) ) else exit( <the nil case> ) end;

@JohnLM Great. This is perfectly reasonable .. for at least two reasons. 1) The challenge is about achieving a solution - dissecting the problem in a way that makes it solvable. 2) Eg in the day 2 and 3 problems, I put the data in Excel to manipulate it around, get a perspective on the contents, and to provide results to crosscheck against while I am only part way towards constructing my approach. I have kept them in my Github repo. 3) Also, some of the challenge is just reading in the data ... which can be sometimes tedious and/or obvious. I have used Excel and Notepad++ to make the data into a Delphi unit holding the info, when moving text with code was unrewarding. PS : There's a cool video from the guy that creates and runs the challenges from very recently. People solve the problems in many different ways - and not just with code. CppNorth - Keynote: Advent of Code, Behind the Scenes - Eric Wastl

Done. I've never used these before. 🙂

I'm lagging a little bit behind ... my solutions are here : https://github.com/pmcgee69/Advent-of-Code-2024/ My ultimate aim is to try to use a functional approach ... and to get ideas for better syntax for Delphi into the future. I'd really like to also solve in Rust and C++, for the learning but also for the ideas on syntax. I will definitely try to lean on eg Claude.io to work out solutions in those two. There's only so much time available!

Something I posted on the ADUG forum ... this C code (when I saw it) was posted on twitter as an amusing post about C. [ Cursed C code ] But after I'd thought about it for a bit, it occurred to me that maybe I could do the same in Delphi. And we can. 🙂 {$APPTYPE CONSOLE} program Project1; type range_struct = record type Tstate = (at_start, in_loop, done); var stop, step, i, start : integer; state : Tstate; function resume() : integer; constructor λ ( _start, _stop : integer; _step : integer = 1); end; constructor range_struct.λ( _start, _stop, _step:integer); begin start := _start; stop := _stop; step := _step; state := at_start; end; function range_struct.resume() : integer; label α,β,δ; begin case state of at_start : goto α; in_loop : goto β; done : goto δ; end; α : i:=start; repeat begin state := in_loop; exit(i); β : i := i + step; end until i >= stop; state := done; δ : exit(0); end; begin var ρ := range_struct.λ(1,20,2); var π := range_struct.λ(2,20,2); for var i in [1..5] do begin writeln('a ',i:2, 'th call : ', ρ.resume); writeln(' b ',i:2, 'th call : ', π.resume); end; writeln; writeln('Mwah ha ha. GOTO is back, baby!'); readln; end. That wasn't the original function-calling code that I had posted. It was only after a bit of mental digestion that I realised that this is (in my opinion) a really good, simplified, understandable model of a coroutine. ... and soon after I found out the original C code was part of an article commenting on c++ coroutines : https://probablydance.com/2021/10/31/c-coroutines-do-not-spark-joy/

It is, in a sense, a bit sad that the lack of user-definable infix operators leads to this sort of "creative interpretation". Shouldn't we complain about this almost as much as about 'With' eg ? This could have (should have?) been implemented by a JoinTo( s1, s2 : string) function. An actual Equality Operator should exhibit the qualities of being reflexive (a=a), symmetric (a=b => b=a), and transitive (a=b, b=c => a=c) (and going back to the first question ... it wouldn't need to return a boolean. Eg some cases, like a partial order, it might return an optional boolean)