Lah numbers: Difference between revisions

=={{header|ALGOL W}}==

Algol W's only integer type is signed 32 bit integers.

<br>

As L(12,2), L(12,3) and L(12,4) are too large for signed 32 bit integers, this sample scales the result by an appropriate power of 10 to enable the table to be printed up to L(12,12). Luckily, the problematic L(12,k) values all have at least 2 trailing zeros.

<lang algolw>begin % calculate Lah numbers upto L( 12, 12 ) %

% sets lahNumber to L( n, k ), lahScale is returned as the power of 10 %

% lahNumber should be multiplied by %

% f must be a table of factorials to at least n %

procedure L ( integer value n, k

; integer array f ( * )

; integer result lahNumber, lahScale

) ;

if n = 0 or k = 0 then begin lahNumber := 0; lahScale := 0 end

else if n = k then begin lahNumber := 1; lahScale := 0 end

else if k = 1 then begin lahNumber := f( n ); lahScale := 0 end

else if k > n then begin lahNumber := 0; lahScale := 0 end

else begin

% general case: ( n! * ( n - 1 )! ) / ( k! * ( k - 1 )! ) / ( n - k )! %

% Algol W has only 32 bit signed integers so we need to avoid overflow %

% we re-arrange the above to: %

% ( n! / k! / ( n - k ) ! ) -- t1 %

% * ( ( n - 1 )! / ( k - 1 )! -- t2 %

% and if necessary, reduce t1 and t2 by powers of 10 %

integer t1, t2, d1, d2, v;

t1 := f( n ) div f( k ) div f( n - k );

t2 := f( n - 1 ) div f( k - 1 );

% calculate the number of digits for t1 and t2 %

lahScale := d1 := d2 := 0;

v := t1; while v > 0 do begin d1 := d1 + 1; v := v div 10 end;

v := t2; while v > 0 do begin d2 := d2 + 1; v := v div 10 end;

if d1 + d2 > 8 then begin

% the result will overflow reduce t1 and t2 by an appropriate power %

% of 10 and set lahScale accordingly %

while t1 rem 10 = 0 do begin lahScale := lahScale + 1; t1 := t1 div 10 end;

while t2 rem 10 = 0 do begin lahScale := lahScale + 1; t2 := t2 div 10 end;

end if_d1_plus_d2_gt_8;

lahNumber := t1 * t2

end L;

% table of factorials up to 12 %

integer array factorial ( 1 :: 12 );

% compute the factorials %

begin

integer f;

f := 1;

for i := 1 until 12 do begin

f := f * i;

factorial( i ) := f

end for_i

end;

% show the Lah numbers %

write( "Unsigned Lah numbers" );

write( "n/k " );

for i := 1 until 12 do writeon( i_w := 11, s_w := 0, i );

for n := 1 until 12 do begin

write( s_w := 2, i_w := 2, n );

for k := 1 until n do begin

integer lahNumber, lahScale;

L( n, k, factorial, lahNumber, lahScale );

writeon( S_W := 0, i_w := 11 - lahScale, lahNumber );

for s := 1 until lahScale do writeon( s_w := 0, "0" )

end for_k

end for_n

end.</lang>

{{out}}

<pre>

Unsigned Lah numbers

n/k 1 2 3 4 5 6 7 8 9 10 11 12

1 1

2 2 1

3 6 6 1

4 24 36 12 1

5 120 240 120 20 1

6 720 1800 1200 300 30 1

7 5040 15120 12600 4200 630 42 1

8 40320 141120 141120 58800 11760 1176 56 1

9 362880 1451520 1693440 846720 211680 28224 2016 72 1

10 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1

11 39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1

12 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1

</pre>