Difference between revisions of "Talk:Lucas number"
From Free Pascal wiki
Jump to navigationJump to searchRogueScholar (talk | contribs) m (Replace deprecated 'enclose' attributes on syntaxhighlight tags with current 'inline' attribute) |
|||
(10 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
+ | == Return type == | ||
Q: Why not use UInt64 as return type for the function. It should be the same on all platforms. | Q: Why not use UInt64 as return type for the function. It should be the same on all platforms. | ||
− | Remark: | + | Remark: It seems a bit strange to me to derive Lucas(n) from Fib(n), because the Fibonacci sequence is just a special case of the Lucas numbers (with starting values 1,1). —[[User:Bart|Bart]] ([[User talk:Bart|talk]]) 19:15, {{#formatdate:10 November 2018|dmy}} (CET) |
− | |||
Here's an example of what I mean: | Here's an example of what I mean: | ||
− | |||
<syntaxhighlight lang="pascal"> | <syntaxhighlight lang="pascal"> | ||
{ | { | ||
Line 47: | Line 46: | ||
end; | end; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | —[[User:Bart|Bart]] ([[User talk:Bart|talk]]) 19:25, {{#formatdate:10 November 2018|dmy}} (CET) | |
+ | |||
+ | I tried to add the lookup tables here, but the wiki insists that they are spam. ;-) | ||
+ | |||
+ | :A: Yeah, I have a [https://www.freepascal.org/docs-html/prog/progse50.html general preference for the CPU's native integer size]. Unlike [[Delphi]] or [[GNU Pascal|GPC]], [[FPC]]'s <syntaxhighlight lang="pascal" inline>integer</syntaxhighlight>/<syntaxhighlight lang="pascal" inline>cardinal</syntaxhighlight> is [[Writing portable code regarding the processor architecture#32 Bit vs. 64_Bit|always of fixed width]], so I used {{Doc|package=RTL|unit=system|identifier=nativeuint|text=<syntaxhighlight lang="pascal" inline>nativeUInt</syntaxhighlight>}}. (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 {{Doc|package=RTL|unit=system|identifier=uint64|text=<syntaxhighlight lang="pascal" inline>uInt64</syntaxhighlight>}}, too, specifically {{Doc|package=RTL|unit=system|identifier=qword|text=<syntaxhighlight lang="pascal" inline>qword</syntaxhighlight>}}, since the former isn't [https://www.freepascal.org/docs-html/ref/refsu4.html#x26-260003.1.1 mentioned in the Reference Guide] but the latter is. | ||
+ | :Don't ask me, but [[User:Djzepi|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 [[Special:Diff/84340|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 <syntaxhighlight lang="pascal" inline>{$mode objFPC}</syntaxhighlight> (extended syntax of <syntaxhighlight lang="pascal" inline>exit</syntaxhighlight> routine). | ||
+ | :* Has <syntaxhighlight lang="pascal" inline>{$modeSwitch exceptions+}</syntaxhighlight> (implicitly set by <syntaxhighlight lang="pascal" inline>{$mode objFPC}</syntaxhighlight> or <syntaxhighlight lang="pascal" inline>{$mode Delphi}</syntaxhighlight>), ''and'' wants them. | ||
+ | :* Has <syntaxhighlight lang="pascal" inline>{$modeSwitch result+}</syntaxhighlight> (implicitly set by <syntaxhighlight lang="pascal" inline>{$mode objFPC}</syntaxhighlight> or <syntaxhighlight lang="pascal" inline>{$mode Delphi}</syntaxhighlight>). | ||
+ | :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 <syntaxhighlight lang="pascal" inline>lucasLeftInverseRange</syntaxhighlight>. In conjunction with <syntaxhighlight lang="pascal" inline>{$rangeChecks on}</syntaxhighlight> an out-of-range error can be easily detected (during development). —[[User:Kai Burghardt|Kai Burghardt]] ([[User talk:Kai Burghardt|talk]]) 20:25, {{#formatdate:11 November 2018|dmy}} (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, <syntaxhighlight lang="pascal" inline>if (N = 0) … 'Lucas function is undefined for 0.'</syntaxhighlight>, well, hell yeah it's defined <math>n=0</math>. It's been all implementations of <syntaxhighlight lang="pascal" inline>lucas</syntaxhighlight> like that. —[[User:Kai Burghardt|Kai Burghardt]] ([[User talk:Kai Burghardt|talk]]) 20:38, {{#formatdate:11 November 2018|dmy}} (CET) | ||
+ | :::I'm off by one then. —[[User:Bart|Bart]] ([[User talk:Bart|talk]]) 23:05, {{#formatdate:11 November 2018|dmy}} (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 <syntaxhighlight lang="pascal" inline>relativePosition</syntaxhighlight> in the [[Fibonacci number#iterative implementation|iterative implementation of <syntaxhighlight lang="pascal" inline>fibonacci</syntaxhighlight>]] producing, IMHO, really readable and comprehensible code. —[[User:Kai Burghardt|Kai Burghardt]] ([[User talk:Kai Burghardt|talk]]) 00:40, {{#formatdate:12 November 2018|dmy}} (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. —[[User:Bart|Bart]] ([[User talk:Bart|talk]]) 18:41, {{#formatdate:12 November 2018|dmy}} (CET) | ||
+ | ::::::OK, so here's the new implementation. It's zero-based, and allows for negative indices. | ||
+ | ::::::<syntaxhighlight lang="pascal"> | ||
+ | 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; | ||
+ | </syntaxhighlight> | ||
+ | ::::::Just for fun. —[[User:Bart|Bart]] ([[User talk:Bart|talk]]) 19:47, {{#formatdate:13 November 2018|dmy}} (CET) | ||
+ | :::::::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 a ''teaching bubble'', as its reputation used to be. I'd leave it as it is, although isn't explained on the page. —[[User:Kai Burghardt|Kai Burghardt]] ([[User talk:Kai Burghardt|talk]]) 22:34, {{#formatdate:15 November 2018|dmy}} (CET) |
Latest revision as of 23:37, 20 September 2023
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 just 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 lookup tables here, but the wiki insists that they are 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 usednativeUInt
. (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 writtenuInt64
, too, specificallyqword
, 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 ofexit
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}
).
- I don't wanna assume one is in
- 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]\displaystyle{ n=0 }[/math]. It's been all implementations oflucas
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 offibonacci
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. —Bart (talk) 18:41, 12 November 2018 (CET)
- OK, so here's the new implementation. It's zero-based, and 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:47, 13 November 2018 (CET)
- 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 a 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)
- 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. —Bart (talk) 18:41, 12 November 2018 (CET)
- I'm off by one then. —Bart (talk) 23:05, 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,