916 Chapter 20.Less-Numerical Algorithms one four one five nine...."For any less frivolous calculation,we would likely never leave base 256(or the thence trivially reachable hexadecimal,octal,or binary bases). We will adopt the convention of storing digit strings in the "human"ordering, that is,with the first stored digit in an array being most significant,the last stored digit being least significant.The opposite convention would,of course,also be possible. "Carries."where we need to partition a number larger than 255 into a low-order byte and a high-order carry,present a minor programming annoyance,solved,in the routines below,by the use of the macros LOBYTE and HIBYTE. It is easy at this point,following Knuth [2].to write a routine for the "fast" arithmetic operations:short addition (adding a single byte to a string),addition, 8 subtraction,short multiplication (multiplying a string by a single byte),short division,ones-complement negation;and a couple of utility operations,copying and left-shifting strings.(On the diskette,these functions are all in the single file mpops.c.) #define LOBYTE(x)((unsigned char)((x)&Oxff)) #define HIBYTE(x)((unsigned char)((x)>>8&Oxff)) Multiple precision arithmetic operations done on character strings,interpreted as radix 256 令 numbers. This set of routines collects the simpler operations. void mpadd(unsigned char w[],unsigned char u[],unsigned char v[],int n) Press. Adds the unsigned radix 256 integers u[1..n]and v[1..n]yielding the unsigned integer ART w[1..n+1] 9 Programs int j; unsigned short ireg=0; for(j=n;j>=1;j--){ ireg-u[j]+v[j]+HIBYTE(ireg); w[j+1]=LOBYTE(ireg); to dir w[1]=H肛BYTE(1reg); 2 19881992 OF SCIENTIFIC COMPUTING(ISBN void mpsub(int is,unsigned char w[],unsigned char u[],unsigned char v], int n) v@cam Subtracts the unsigned radix 256 integer v[1..n]from u[1..n]yielding the unsigned integer Numerical Recipes 10-621 w[1..n].If the result is negative (wraps around),is is returned as-1;otherwise it is returned as 0. 43108 int j; unsigned short ireg=256; (outside 膜 for (j=n;j>=1;j--){ ireg=255+u[i]-v[i]+HIBYTE(ireg); North Software. w[j]=LOBYTE(ireg); *is=HIBYTE(ireg)-1; void mpsad(unsigned char w[],unsigned char u[],int n,int iv) Short addition:the integer iv (in the range 0<iv 255)is added to the unsigned radix 256 integer u[1..n],yielding w[1..n+1]. int j; unsigned short ireg; 1reg=256*1v;916 Chapter 20. Less-Numerical Algorithms Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). one four one five nine... .” For any less frivolous calculation, we would likely never leave base 256 (or the thence trivially reachable hexadecimal, octal, or binary bases). We will adopt the convention of storing digit strings in the “human” ordering, that is, with the first stored digit in an array being most significant, the last stored digit being least significant. The opposite convention would, of course, also be possible. “Carries,” where we need to partition a number larger than 255 into a low-order byte and a high-order carry, present a minor programming annoyance, solved, in the routines below, by the use of the macros LOBYTE and HIBYTE. It is easy at this point, following Knuth [2], to write a routine for the “fast” arithmetic operations: short addition (adding a single byte to a string), addition, subtraction, short multiplication (multiplying a string by a single byte), short division, ones-complement negation; and a couple of utility operations, copying and left-shifting strings. (On the diskette, these functions are all in the single file mpops.c.) #define LOBYTE(x) ((unsigned char) ((x) & 0xff)) #define HIBYTE(x) ((unsigned char) ((x) >> 8 & 0xff)) Multiple precision arithmetic operations done on character strings, interpreted as radix 256 numbers. This set of routines collects the simpler operations. void mpadd(unsigned char w[], unsigned char u[], unsigned char v[], int n) Adds the unsigned radix 256 integers u[1..n] and v[1..n] yielding the unsigned integer w[1..n+1]. { int j; unsigned short ireg=0; for (j=n;j>=1;j--) { ireg=u[j]+v[j]+HIBYTE(ireg); w[j+1]=LOBYTE(ireg); } w[1]=HIBYTE(ireg); } void mpsub(int *is, unsigned char w[], unsigned char u[], unsigned char v[], int n) Subtracts the unsigned radix 256 integer v[1..n] from u[1..n] yielding the unsigned integer w[1..n]. If the result is negative (wraps around), is is returned as −1; otherwise it is returned as 0. { int j; unsigned short ireg=256; for (j=n;j>=1;j--) { ireg=255+u[j]-v[j]+HIBYTE(ireg); w[j]=LOBYTE(ireg); } *is=HIBYTE(ireg)-1; } void mpsad(unsigned char w[], unsigned char u[], int n, int iv) Short addition: the integer iv (in the range 0 ≤ iv ≤ 255) is added to the unsigned radix 256 integer u[1..n], yielding w[1..n+1]. { int j; unsigned short ireg; ireg=256*iv;