Long multiplication: Difference between revisions
Added PL/M
(Added PL/M) |
|||
Line 4,135:
18446744073709551616
340282366920938463463374607431768211456
</pre>
=={{header|PL/M}}==
{{Trans|ALGOL W}} Uses bytes instead of integers to hold the digits.
Tested using a PLM286 to C converter and a simple I/O library.
<lang plm>LONGMULT: DO;
/* long multiplication of large integers */
/* large integers are represented by arrays of bytes whose values are */
/* a single decimal digit of the number */
/* the least significant digits of the large integer are in element 1 */
/* element 0 should contain 0 if the number is positive, 1 if negative */
/* External I/O routines */
WRITE$STRING: PROCEDURE( S ) EXTERNAL; DECLARE S POINTER END WRITE$STRING;
WRITE$CHAR: PROCEDURE( C ) EXTERNAL; DECLARE C BYTE END WRITE$CHAR;
WRITE$NL: PROCEDURE EXTERNAL; END WRITE$NL;
/* End external routines */
DECLARE DIGIT$BASE LITERALLY '10';
DECLARE DIGIT$COUNT LITERALLY '49'; /* allows up to 48 digits */
/* - enough for the task */
DECLARE LARGE$INTEGER LITERALLY '(49)BYTE';
/* returns the position of the highest non-zero digit of the large */
/* integer a with n digits */
HIGHEST$NONZERO$DIGIT$POSITION: PROCEDURE( A, N ) BYTE;
DECLARE A LARGE$INTEGER;
DECLARE N BYTE;
DECLARE AMAX BYTE;
AMAX = N;
DO WHILE AMAX >= 1 AND A( AMAX ) = 0; AMAX = AMAX - 1; END;
RETURN AMAX;
END HIGHEST$NONZERO$DIGIT$POSITION ;
/* multiplies the large integer in b by the integer a, the result */
/* is added to c, starting from start */
/* overflow is ignored */
MULTIPLY$ELEMENT: PROCEDURE( A, B, C, START );
DECLARE ( B, C ) LARGE$INTEGER;
DECLARE ( A, START ) BYTE;
DECLARE ( CDIGIT, CARRY, BPOS, CPOS ) BYTE;
CARRY = 0;
CPOS = START;
DO BPOS = 1 TO HIGHEST$NONZERO$DIGIT$POSITION( B, DIGIT$COUNT - START );
CDIGIT = C( CPOS ) + ( A * B( BPOS ) ) + CARRY;
IF CDIGIT < DIGIT$BASE THEN CARRY = 0;
ELSE DO;
/* have digits to carry */
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 ) = CARRY;
END MULTIPLY$ELEMENT ;
/* implements long multiplication, c is set to a * b */
/* c can be the same array as a or b */
LONG$MULTIPLY: PROCEDURE( A, B, C );
DECLARE ( A, B, C ) LARGE$INTEGER;
DECLARE MRESULT LARGE$INTEGER;
DECLARE RPOS BYTE;
/* the result will be computed in mResult, allowing a or b to be c */
DO RPOS = 1 TO DIGIT$COUNT - 1; MRESULT( RPOS ) = 0; END;
/* multiply and add each digit to the result */
DO RPOS = 1 TO HIGHEST$NONZERO$DIGIT$POSITION( A, DIGIT$COUNT - 1 );
IF A( RPOS ) <> 0 THEN DO;
CALL MULTIPLY$ELEMENT( A( RPOS ), B, MRESULT, RPOS );
END;
END;
/* return the result in c */
DO RPOS = 1 TO DIGIT$COUNT - 1; C( RPOS ) = MRESULT( RPOS ); END;
C( 0 ) = A( 0 ) XOR B( 0 ); /* handle the sign */
END;
/* writes the decimal value of a large integer a with n digits */
WRITE$LARGE$INTEGER: PROCEDURE( A );
DECLARE A LARGE$INTEGER;
DECLARE ( AMAX, APOS ) BYTE;
AMAX = HIGHEST$NONZERO$DIGIT$POSITION( A, DIGIT$COUNT - 1 );
IF AMAX < 1 THEN CALL WRITE$CHAR( '0' );
ELSE DO;
/* the large integer is non-zero */
IF A( 0 ) <> 0 THEN CALL WRITE$CHAR( '-' );
APOS = AMAX;
CALL WRITE$CHAR( A( APOS ) + '0' ); /* highest digit */
DO WHILE APOS > 1;
APOS = APOS - 1;
CALL WRITE$CHAR( A( APOS ) + '0' );
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>
2^128: 340282366920938463463374607431768211456
</pre>
| |||