|
=={{header|PL/M}}==
{{Trans|ALGOLBased on the Algol W}} sample, Uses bytes instead of integers to hold the digits.
<lang plm>100H: /* LONG MULTIPLICATION OF LARGE INTEGERS */
Tested using a PLM286 to C converter and a simple I/O library.
/* LARGE INTEGERS ARE REPRESENTED BY ARRAYS OF BYTES WHOSE VALUES ARE */
<lang plm>LONGMULT: DO;
/* longA SINGLE DECIMAL DIGIT OF multiplicationTHE ofNUMBER large integers */
/* THE LEAST SIGNIFICANT DIGIT OF THE LARGE INTEGER IS IN ELEMENT 1 */
/* large integers are represented by arrays of bytes whose values are */
/* a single decimal digit of the number ELEMENT 0 CONTAINS THE NUMBER OF DIGITS THE NUMBER HAS */
BDOS: PROCEDURE( FN, ARG ); /* CP/M BDOS SYSTEM CALL */
/* the least significant digits of the large integer are in element 1 */
DECLARE FN BYTE, ARG ADDRESS;
/* element 0 should contain 0 if the number is positive, 1 if negative */
GOTO 5;
/* External I/O routines */
END BDOS;
WRITE$STRING: PROCEDURE( S ) EXTERNAL; DECLARE S POINTER; END WRITE$STRING;
WRITEPRINT$CHAR: PROCEDURE( C ) EXTERNAL; DECLARE C BYTE; ENDCALL WRITE$CHARBDOS( 2, C ); END;
WRITEPRINT$NLSTRING: PROCEDURE( S ); DECLARE S EXTERNALADDRESS; CALL BDOS( 9, S ); END WRITE$NL;
DECLARE PRINT$NL LITERALLY 'PRINT$STRING( .( 0DH, 0AH, ''$'' ) )';
/* End external routines */
DECLARE DIGIT$BASE LITERALLY '10';
DECLARE DIGITLONG$COUNT INTEGER LITERALLY '49(201)BYTE'; /* allows up to 48 digits */
DECLARE DIGIT$BASE LITERALLY '10';
/* - enough for the task */
DECLARE LARGE$INTEGER LITERALLY '(49)BYTE';
/* PRINTS A LONG INTEGER */
/* returns the position of the highest non-zero digit of the large */
PRINT$LONG$INTEGER: PROCEDURE( N$PTR );
/* integer a with n digits */
DECLARE N$PTR ADDRESS;
HIGHEST$NONZERO$DIGIT$POSITION: PROCEDURE( A$PTR, N ) BYTE;
DECLARE N DECLAREBASED AN$PTR POINTERLONG$INTEGER;
DECLARE N( D, F ) BYTE;
F = DECLAREN( A0 BASED A$PTR LARGE$INTEGER);
DO D DECLARE= AMAX1 BYTETO N( 0 );
AMAX CALL =PRINT$CHAR( N( F ) + '0' );
DO WHILEF AMAX >= 1 AND A( AMAX ) = 0; AMAX = AMAXF - 1; END;
RETURN AMAXEND;
END HIGHESTPRINT$NONZEROLONG$DIGIT$POSITION INTEGER;
/* multipliesIMPLEMENTS LONG MULTIPLICATION, C IS SET TO A * B the large integer in b by the integer a, the result */
/* is added toC c,CAN startingBE fromTHE startSAME LONG$INTEGER AS A OR B */
LONG$MULTIPLY: PROCEDURE( A$PTR, B$PTR, C$PTR );
/* overflow is ignored */
MULTIPLY$ELEMENT: PROCEDURE DECLARE ( A$PTR, B$PTR, C$PTR, START ) ADDRESS;
DECLARE ( A BASED A$PTR, B BASED B$PTR, C BASED C$PTR ) POINTERLONG$INTEGER;
DECLARE ( A, START ) MRESULT BYTELONG$INTEGER;
DECLARE ( B BASED B$PTR, C BASEDRPOS C$PTR ) LARGE$INTEGERBYTE;
DECLARE ( CDIGIT, CARRY, BPOS, CPOS ) BYTE;
/* MULTIPLIES THE LONG INTEGER IN B BY THE INTEGER A, THE RESULT */
CARRY = 0;
/* IS ADDED TO C, STARTING FROM DIGIT START */
CPOS = START;
/* OVERFLOW IS IGNORED */
DO BPOS = 1 TO HIGHEST$NONZERO$DIGIT$POSITION( B$PTR, DIGIT$COUNT - START );
MULTIPLY$ELEMENT: PROCEDURE( A, B$PTR, C$PTR, START );
CDIGIT = C( CPOS ) + ( A * B( BPOS ) ) + CARRY;
DECLARE ( B$PTR, C$PTR ) IF CDIGIT < DIGIT$BASE THEN CARRY = 0ADDRESS;
DECLARE ( A, START ) BYTE;
DECLARE ( B BASED B$PTR, C BASED C$PTR ) LONG$INTEGER;
DECLARE ( CDIGIT, D$CARRY, BPOS, CPOS ) BYTE;
D$CARRY = 0;
CPOS = START;
DO BPOS = 1 TO B( 0 );
CDIGIT = C( CPOS ) + ( A * B( BPOS ) ) + D$CARRY;
IF CDIGIT < DIGIT$BASE THEN D$CARRY = 0;
ELSE DO;
/* haveHAVE DIGITS digitsTO toCARRY carry */
D$CARRY = CDIGIT / DIGIT$BASE;
CDIGIT = CDIGIT MOD DIGIT$BASE;
END;
C( CPOS ) = CDIGIT;
CPOS = CPOS + 1;
END;
IF CPOS <= ( DIGIT$COUNT - 1 ) THEN C( CPOS ) = D$CARRY;
/* REMOVE LEADING ZEROS BUT IF THE NUMBER IS 0, KEEP THE FINAL 0 */
END MULTIPLY$ELEMENT ;
/* implements long multiplication, c isDO setWHILE( toCPOS a> *1 bAND C( CPOS ) = 0 */);
CPOS = CPOS - 1;
/* c can be the same array as a or b */
END;
LONG$MULTIPLY: PROCEDURE( A$PTR, B$PTR, C$PTR );
DECLARE C( A$PTR, B$PTR, C$PTR0 ) = POINTERCPOS;
END MULTIPLY$ELEMENT ;
DECLARE ( A BASED A$PTR
, B BASED B$PTR
/* THE RESULT WILL BE COMPUTED IN MRESULT, ALLOWING A ,OR CB BASEDTO BE C$PTR */
DO RPOS = 1 TO LAST( MRESULT ); MRESULT( RPOS ) = 0; LARGE$INTEGEREND;
/* MULTIPLY DECLAREBY MRESULTEACH DIGIT AND ADD TO THE RESULT LARGE$INTEGER; */
DECLAREDO RPOS = 1 TO A( 0 BYTE);
/* theIF resultA( willRPOS be) computed<> in0 mResult,THEN allowing a or b to be c */DO;
DO RPOS = 1 TOCALL DIGITMULTIPLY$COUNTELEMENT( - 1; MRESULTA( RPOS ), =B$PTR, 0;.MRESULT, ENDRPOS );
END;
/* multiply and add each digit to the result */
END;
DO RPOS = 1 TO HIGHEST$NONZERO$DIGIT$POSITION( A$PTR, DIGIT$COUNT - 1 );
/* RETURN THE RESULT IN C */
IF A( RPOS ) <> 0 THEN DO;
DO RPOS = 0 TO MRESULT( 0 ); CALL MULTIPLY$ELEMENT( AC( RPOS ), B$PTR,= @MRESULT,( RPOS ); END;
END;
END;
/* returnCALCULATE theAND resultOUTPUT in2^128 c */
DECLARE ( TWO$TO$64, TWO$TO$128 ) LONG$INTEGER;
DO RPOS = 1 TO DIGIT$COUNT - 1; C( RPOS ) = MRESULT( RPOS ); END;
DECLARE ( PWR, TPOS ) BYTE;
C( 0 ) = A( 0 ) XOR B( 0 ); /* handle the sign */
/* CONSTRUCT 2^64 IN TWO$TO$64 */
END;
DO TPOS = 0 TO LAST( TWO$TO$64 ); TWO$TO$64( TPOS ) = 0; END;
/* writes the decimal value of a large integer a with n digits */
WRITETWO$LARGETO$INTEGER: PROCEDURE64( A$PTR0 ) = 1;
DECLARE ATWO$PTR TO$64( 1 ) = POINTER2;
PWR DECLARE A BASED A$PTR LARGE$INTEGER= 1;
DO WHILE PWR < 64;
DECLARE ( AMAX, APOS ) BYTE;
CALL LONG$MULTIPLY( .TWO$TO$64, .TWO$TO$64, .TWO$TO$64 );
AMAX = HIGHEST$NONZERO$DIGIT$POSITION( A$PTR, DIGIT$COUNT - 1 );
PWR IF= AMAXPWR <+ 1 THEN CALL WRITE$CHAR( '0' )PWR;
ELSE DOEND;
/* CONSTRUCT 2^128 /* the large integer is non-zero */
TWO$TO$128( 0 ) = 1;
IF A( 0 ) <> 0 THEN CALL WRITE$CHAR( '-' );
TWO$TO$128( 1 APOS) = AMAX0;
CALL LONG$MULTIPLY( .TWO$TO$64, .TWO$TO$64, .TWO$TO$128 );
CALL WRITE$CHAR( A( APOS ) + '0' ); /* highest digit */
CALL PRINT$STRING( .( '2', 05EH, '128: $' ) ); /* 05EH = "^" IN ASCII */
DO WHILE APOS > 1;
CALL PRINT$LONG$INTEGER( .TWO$TO$128 );
APOS = APOS - 1;
CALL PRINT$NL;
CALL WRITE$CHAR( A( APOS ) + '0' );
EOF</lang>
END;
END;
END WRITE$LARGE$INTEGER ;
/* calculate and output 2^128 */
MAIN: PROCEDURE;
DECLARE ( TWOTO64, TWOTO128 ) LARGE$INTEGER;
DECLARE ( PWR, TPOS ) BYTE;
/* construct 2^64 in twoTo64 */
DO TPOS = 0 TO DIGIT$COUNT - 1; TWOTO64( TPOS ) = 0; END;
TWOTO64( 1 ) = 2;
PWR = 1;
DO WHILE PWR < 64;
CALL LONG$MULTIPLY( @TWOTO64, @TWOTO64, @TWOTO64 );
PWR = PWR + PWR;
END;
/* construct 2^128 */
CALL LONG$MULTIPLY( @TWOTO64, @TWOTO64, @TWOTO128 );
CALL WRITE$STRING( @( '2^128: ', 0 ) );
CALL WRITE$LARGE$INTEGER( @TWOTO128 );
CALL WRITE$NL();
END MAIN;
END LONGMULT;</lang>
{{out}}
<pre>
|