Talk:Lucas number

From Free Pascal wiki

return type

Q: Why not use UInt64 as return type for the function. It should be the same on all platforms.

Remark: it seems a bit strange to me to derive Lucas(n) from Fib(n), because the Fibonacci sequence is jus a special case of the Lucas numbers (with starting values 1,1). --Bart (talk) 19:15, 10 November 2018 (CET)


Here's an example of what I mean:

{
A more general form of the Lucas series, where the 2 starting values
can be set using parameters
}
function LucasGen(L1, L2, N: UInt64): UInt64;
var
  i, LucMin1, LucMin2: UInt64;
begin
  if (N = 0) then
    Raise ERangeError.Create('Lucas function is undefined for 0.');
  if (N = 1) then
    Exit(L1)
  else if (N = 2) then
    Exit(L2)
  else
  begin
    LucMin1 := L2;
    LucMin2 := L1;
    i := 2;
    while (i <> N) do
    begin
      Inc(i);
      Result := LucMin2 + LucMin1;
      LucMin2 := LucMin1;
      LucMin1 := Result;
    end;
  end;
end;

function Lucas(N: UInt64): UInt64;
begin
  Result := LucasGen(2,1,N);
end;


function Fib(N: UInt64): UInt64;
begin
  Result := LucasGen(1,1,N);  
end;

--Bart (talk) 19:25, 10 November 2018 (CET)

I tried to add the lookuptables here, but the wiki insists that is spam ;-)

A: Yeah, I have a general preference for the CPU's native integer size. Unlike Delphi or GPC, FPC's integer/cardinal is always of fixed width, so I used nativeUInt. [However, according to its documentation it's only either 32 or 64 bits, no more, no less, so I can't put code in there for other case.] I just wanna raise awareness for such issues (although it is potentially confusing [hence your question]). I of course would have written uInt64, too, specifically qword, since the former isn't mentioned in the Reference Guide but the latter is.
Don't ask me, but Djzepi created both Fibonacci number and Lucas number. However, I guess it's the other way around: I regard Fibonacci as a general case, and Lucas being a specialization. He introduced calculation of Lucas numbers based on Fibonacci in the page's initial version.
Regarding your code: I want to keep it simple, the examples in the wiki. This implies:
  • I don't wanna assume one is in {$mode objFPC} (extended syntax of exit routine)
  • has {$modeSwitch exceptions+} (implicitly set by {$mode objFPC} or {$mode Delphi}), and wants them
  • has {$modeSwitch result+} (implicitly set by {$mode objFPC} or {$mode Delphi}).
Therefore I regard my implementation as *the best*. [Surprise!] No. Kidding aside, but seriously, I think it is important to embrace robustness of routines, a general notion I derive from Pascal's strictness. You can discern this in lucasLeftInverseRange. In conjunction with {$rangeChecks on} an out-of-range error can be easily detected (during development).
Kai Burghardt (talk) 20:25, 11 November 2018 (CET)
OK, I see. I consulted Wikipedia. I stand corrected. You're right, Lucas sequences being the generic case, and Fibonacci a special case. However, if (N = 0)  'Lucas function is undefined for 0.', well, hell yeah it's defined [math]n=0[/math]. It's been all implementations of lucas like that. Kai Burghardt (talk) 20:38, 11 November 2018 (CET)
I'm off by one then. --Bart (talk) 23:05, 11 November 2018 (CET)
You otherwise agree? My answer isn't like a set in stone argument, but a “plea” for a certain policy.
I especially like the relativePosition in the iterative implementation of fibonacci producing IMHO really readable and comprehensible code. Kai Burghardt (talk) 00:40, 12 November 2018 (CET)
No, I don't agree (talking about the use of NativeInt here). It makes the example unnecessarily complex IMHO. But it's perfectly fine to disagree on that.
Yeah, I see, it isn't really part of the problem, of the task: “calculate n-th Lucas number”. On the other hand I wanna write examples, promote code, which you actually would see in a production program. I don't wanna put Pascal in teaching bubble as its reputation used to be. I'd leave it as it is, although isn't explained on the page. Kai Burghardt (talk) 22:34, 15 November 2018 (CET)



OK, so here's the new implementation. It's zero based, allows for negative indices.

type
  LucasRange = -90..90;
  FibRange = -92..92;

function LucasGen(L0, L1, N: Integer; AllowNegativeIndex: Boolean = False): Int64;
var
  i: Integer;
  LucMin1, LucMin2: Int64;
  IsNegative: Boolean;
begin
  IsNegative := (N < 0);
  if (not AllowNegativeIndex) and IsNegative then
    Raise ERangeError.Create('Range check error: to allow for negative indexes in LucasGen(), you must set the AllowNegativeIndex parameter to TRUE.');
  N := Abs(N);
  if (N = 0) then
  begin
    Result := L0
  end
  else if (N = 1) then
  begin
    Result := L1
  end
  else
  begin
    LucMin1 := L1;
    LucMin2 := L0;
    i := 1;
    while (i <> N) do
    begin
      Inc(i);
      Result := LucMin2 + LucMin1;
      LucMin2 := LucMin1;
      LucMin1 := Result;
    end;
  end;
  if IsNegative and Odd(N) then
    Result := -Result; //(Lucas(-N) = (-1^N)*Lucas(N);
end;

Just for fun. --Bart (talk) 19:35, 13 November 2018 (CET)