(HP71B) integer determinant
02-21-2024, 08:23 AM
Post: #6
 J-F Garnier Senior Member Posts: 965 Joined: Dec 2013
RE: (HP71B) integer determinant
(02-16-2024 10:36 PM)Albert Chan Wrote:  HP71B Code translated from @pycoder's Python code

...
120 X=P*M(J,K)-M(J,I)*M(I,K) @ M(J,K)=IROUND(X/P0)
...

Hi Albert,

You had to artificially round the X/P0 term to an integer, because the terms P*M(J,K) and M(J,I)*M(I,K) exceed 1e12 at some points (up to 1e15).
This seems to be an advantage of the Bird's algorithm used by Valentin in his SRC #014 to have all matrix terms less than 1e10 (for Valentin's examples of course) so the algorithm runs fine on a 10-digit machine such as the 15c.
To be more precise, intermediate values during inner products of the matrix multiplication may be up to 1e12, but this is correctly handled by the internal extended accuracy code used during this operation (13 digits on the 15c), and there is no loss of data.

Here is my HP-71B implementation of the Bird's algorithm (a translation/adaptation of Valentin's code):

10 ! SRC14B
20 OPTION BASE 1
30 INPUT "N? ";N
40 DIM A(N,N)
50 MAT INPUT A
100 CALL BDET(A,D)
110 PRINT "DET=";D
120 END
130 !
430 SUB BDET(A(,),D) ! Bird's algorithm
440   N=UBND(A,1) @ DIM B(N,N),E(N,N)
460   MAT B=A
470   FOR K=1 TO N-1
480     MAT E=B
490     FOR I=2 TO N @ FOR J=1 TO I-1 @ E(I,J)=0 @ NEXT J @ NEXT I
520     E(N,N)=0 @ X=0-B(N,N)
530     FOR I=N-1 TO 1 STEP -1 @ E(I,I)=X @ X=X-B(I,I) @ NEXT I
580     MAT E=-E @ MAT B=E*A
590  !  PRINT "B=" @ MAT PRINT B; ! for debug
600   NEXT K
610   D=B(1,1)
620 END SUB

The examples I posted in Valentin's thread are failing with the 71B implementation of the Bareiss' algorithm, but are correct processed with this Bird's implementation.

J-F

Ref: birds-algorithm-for-computing-determinants
 « Next Oldest | Next Newest »

 Messages In This Thread (HP71B) integer determinant - Albert Chan - 02-16-2024, 10:36 PM RE: (HP71B) integer determinant - Albert Chan - 02-16-2024, 11:16 PM RE: (HP71B) integer determinant - Albert Chan - 02-17-2024, 05:03 PM RE: (HP71B) integer determinant - robve - 02-18-2024, 03:05 PM RE: (HP71B) integer determinant - Albert Chan - 02-18-2024, 03:33 PM RE: (HP71B) integer determinant - J-F Garnier - 02-21-2024 08:23 AM RE: (HP71B) integer determinant - Albert Chan - 02-21-2024, 01:31 PM

User(s) browsing this thread: 1 Guest(s)