diff options
Diffstat (limited to 'Master/texmf-dist/doc/generic/apnum/apnum.d')
| -rw-r--r-- | Master/texmf-dist/doc/generic/apnum/apnum.d | 133 |
1 files changed, 35 insertions, 98 deletions
diff --git a/Master/texmf-dist/doc/generic/apnum/apnum.d b/Master/texmf-dist/doc/generic/apnum/apnum.d index 4c7b65572f2..bb54c03037f 100644 --- a/Master/texmf-dist/doc/generic/apnum/apnum.d +++ b/Master/texmf-dist/doc/generic/apnum/apnum.d @@ -10,7 +10,7 @@ \input utf8off \clearmubyte % use pdfcsplain -\def\projectversion{1.0 2014} +\def\projectversion{1.1 Jan 2015} \def\headtitle{Arbitrary Precision Numbers} \widowpenalty=10000 @@ -503,11 +503,11 @@ If there is a problem (level of brackets less than zero, level of brackets not equal to zero at the end of the expression, unknown operator) we print an error using "\apEVALerror" macro. -The "\next" is set to "\apEVALb", i.e.\ scanner returns back to the state of +The "\apNext" is set to "\apEVALb", i.e.\ scanner returns back to the state of reading the operand. But exceptions exist: if the ")" is found then priority is decreased and the macro "\apEVALo" is executed again. If the end of the "<expression>" is found then the loop is ended by -"\let\next=\relax". +"\let\apNext=\relax". \inext{apEVALo}{\count=2 ^^B\cbrace}{++} @@ -545,7 +545,7 @@ executed after group by the "\apEVALa" macro. The macro \db apEVALerror "<string>" prints an error message. We decide to be better to print only "\message", no "\errmessage". The "\tmpb" is -prepared to create "\OUT" as "??" and the "\next" macro is set in order to skip +prepared to create "\OUT" as "??" and the "\apNext" macro is set in order to skip the rest of the scanned "<expression>". \inext{apEVALerror}{^^B\cbrace}{++} @@ -736,7 +736,7 @@ The macro \db apPLUSa does the following work: \ilabel[plus:ba] {apPLUSg} \ilabel[plus:bb] {apnumC=-} \ilabel[plus:G] {apnumG=0} -\ilabel[plus:next] {next=} +\ilabel[plus:next] {apNext=} \ilabel[plus:X] {apnumX=0} \ilabel[plus:fa] {00123} \ilabel[plus:fb] {apPLUSy} @@ -784,10 +784,10 @@ The macro \db apPLUSa does the following work: \item * The transmission calculation is different for addition and subtraction. If the subtraction is processed then the sign of the result is set (using the value "\apnumG") and the "\apPLUSm" for transmissions is - prepared. Else the "\apPLUSp" for transmissions is prepared as the "\next" macro + prepared. Else the "\apPLUSp" for transmissions is prepared as the "\apNext" macro (line~\cite[plus:next]) \item * The result of the first pass is expanded in the input stream and the - "\next" (i.e.\ transmissions calculation) is activated at line~\cite[plus:X]. + "\apNext" (i.e.\ transmissions calculation) is activated at line~\cite[plus:X]. \item * if the result is in the form ".000123", then the decimal point and the trailing zeros have to be inserted. Else the trailing zeros from the left side of the result have to be removed by "\apPLUSy". This macro adds @@ -839,7 +839,7 @@ sign of the result to the "\apnumG" and (maybe) exchanges the "\apPLUSxA" and "\apPLUSxB" macros (by the \db apPLUSg macro) in order to the internal result of the subtraction will be always non-negative. -If the end of input stream is reached, then "\next" (used at line~\cite[plus:nn]) +If the end of input stream is reached, then "\apNext" (used at line~\cite[plus:nn]) is reset from its original value "\apPLUSc" to the \db apPLUSd where the "\apnumY" is simply set to zero. The reading from input stream is finished. This occurs when there are more Digits after decimal point in the second @@ -848,7 +848,7 @@ operand than in the first one. If the end of input stream is reached and the \db apPLUSf macro removes the rest of input stream and the first pass of the calculation is done. -\ilabel[plus:nn] {next^^E} +\ilabel[plus:nn] {apNext^^E} \inext{apPLUSc}{def\nb apPLUSh}{++} Why there is a complication about reading one parameter from input stream @@ -1252,7 +1252,7 @@ macros and does the following work: \ilabel[div:outa] {edef\nb OUT} \ilabel[div:outb] {apADDzeros} \ilabel[div:z] {apnumZ=} -\ilabel[div:next] {next=} +\ilabel[div:next] {apNext=} \ilabel[div:add] {apnumZ=\nb apnumD} \ilabel[div:rema] {apDIVv} \ilabel[div:remb] {apROLLa} @@ -1413,7 +1413,7 @@ case, we put it to the input stream using "\expandafter\apDIVh\tmpa" followed by four "\apNL"s (which simply expands zero digit) followed by stop-mark. The "\apDIVh" reads one Digit from input stream. Else we put only the stop-mark to the input stream and run the -"\apDIVi". The "\nexti" is set to the "\apDIVi", so the macro "\apDIVh" will +"\apDIVi". The "\apNexti" is set to the "\apDIVi", so the macro "\apDIVh" will be skipped forever and no new Digit is read from input stream. \inext{apDIVg}{^^B\cbrace}{++} @@ -1421,7 +1421,7 @@ be skipped forever and no new Digit is read from input stream. The macro \db apDIVh reads one Digit from data stream (from the rest of the dividend) and saves it to the "\apnumZ" register. If the stop-mark is reached (this is recognized that the last digit is the "\apNL"), -then "\nexti" is set to "\apDIVi", so the "\apDIVh" is never +then "\apNexti" is set to "\apDIVi", so the "\apDIVh" is never processed again. \inext{apDIVh}{^^B\cbrace}{++} @@ -1541,42 +1541,26 @@ is simple but slow. The goal of this section is to present the power to the integer with some optimizations. Let $a$ is the base of the powering computation and $d_1, d_2, d_3, \dots, -d_n$ are decimal digits of the exponent (in reverse order). Then +d_n$ are binary digits of the exponent (in reverse order). Then $$ - p = a^{1\,{d_1}+10\,{d_2}+100\,{d_3}+\cdots+10^{n-1}\,{d_n}} = - (a^1)^{d_1}\cdot(a^{10})^{d_2}\cdot(a^{100})^{d_3}\cdot (a^{10^{n-1}})^{d_n}. + p = a^{1\,{d_1}+2\,{d_2}+2^2\,{d_3}+\cdots+2^{n-1}\,{d_n}} = + (a^1)^{d_1}\cdot(a^2)^{d_2}\cdot(a^{2^2})^{d_3}\cdot (a^{2^{n-1}})^{d_n}. $$ -We can see from previous equation that the $p$ can be computed by the +If $d_i=0$ then $z^{d_i}$ is one and this can be omitted from the queue of +multiplications. If $d_i=1$ then we keep $z^{d_i}$ as $z$ in the queue. +We can see from this that the $p$ can be computed by the following algorithm: \begtt -p := 1 -for (i=1; i<n+1; i++) { - if (i>1) a := a^10; - if (d[i]>0) p := p * a^d[i]; +(* "a" is initialized as the base, "e" as the exponent *) +p := 1; +while (e>0) { + if (e%2) p := p*a; + e := e/2; + if (e>0) a := a*a; } +(* "p" includes the result *) \endtt -% -We have a problem that we are playing with the number system of the base 10. -The calculation of "a:=a^10" is not such trivial as a similar task in -binary system. We have to calculate all new decimal digits by -multiplications. But we needn't to do 9 multiplications, because $a^{10} = -(a\,(a^2)^2)^2$, i.e. only four multiplications are needed. Suppose two functions -"pow2(x){x:=x*x}" and "mul(x){x:=a*x}". We can reuse the information from the -previous step where "a^d[i-1]" is already computed. For example $d_{i-1}$ -from previous step was 4 and this was computed by "b:=a;" "pow2(b);" "pow2(b);". -Then we can compute $a^{10}$ from the previous step by -"mul(b);" "pow(b);" "a:=b". The algorithm above can be more specified by: - -\begtt -p := 1; a := base; b := a -for (i=1; i<n+1; i++) { - if (i>1) { use previous value of b and functions mul(b), pow2(b) - in order to b = a^10; - a := b; } - if (d[i]>0) { use functions mul(b), pow2(b) in order to b = a^d[i]; - p := p * b; } -\endtt The macro \db apPOWa does the following work. @@ -1591,7 +1575,6 @@ The macro \db apPOWa does the following work. \ilabel[pow:ab] {ifcase} \ilabel[pow:ba] {apMULb} \ilabel[pow:bb] {*.\nb OUT} -\ilabel[pow:c] {apMULc} \ilabel[pow:p] {1*} \ilabel[pow:rev] {apREV} \ilabel[pow:b] {apPOWb} @@ -1622,19 +1605,12 @@ The macro \db apPOWa does the following work. (lines~\cite[pow:aa] to~\cite[pow:ab]). \item * The base is saved in interleaved reversed format (like in "\apMULa") into the "\OUT" macro by the "\apMULb" macro. Let it be the - $b$ value from our algorithm described above + $a$ value from our algorithm described above (lines~\cite[pow:ba] and~\cite[pow:bb]). -\item * The same base is saved to "\tmpa" in reversed (but non-interleaved) - format by "\apMULc". Let it be the $a$ value from our algorithm - (line~\cite[pow:c]). \item * The initial value of $p=1$ from our algorithm is set in interleaved format into "\tmpc" macro (line~\cite[pow:p]). -\item * In brief: $a={}$"\tmpa", $b={}$"\OUT", $p={}$"\tmpc". -\item * The decimal digits of the exponent in "\tmpb" are reversed - (line~\cite[pow:rev]). -\item * The main loop described above is processed by putting decimal digits - of the exponent into input stream in reversed order and processing the "\apPOWb" macro. +\item * The main loop described above is processed by "\apPOWb" macro. (line~\cite[pow:b]). \item * The result in "\tmpc" is converted into human readable form by the "\apPOWg" macro and it is stored into the "\OUT" macro @@ -1650,50 +1626,18 @@ The macro \db apPOWa does the following work. \inext{apPOWa}{^^B\cbrace}{++} -The macro \db apPOWb is the body of the loop in the algorithm described above. The part -"\ifnum\apnumE"{\tt\char`<}"10" is processed only for second and next digits because the -"\apnumE" is initialized as 10 in the "\apPOWa" macro and it includes the digit of -the exponent from the previous step when next step is processed. -This is equivalent to "if(i"{\tt\char`>}"1)" from -algorithm described above. The sequence of functions "mul(b)" and "pow2(b)" -are set for each value of the digit of the exponent in the "\ifcase" -arguments. For example, the digit from the previous step was~4, i.e.\ -$b=a^4$. Then "\apPOWc"~"mp." is processed. This expands to "\apPOWm" "\apPOWp" -which are macros where the functions "mul(b)" and "pow2(b)" are -implemented. The following operations is processed: "b:=a*b" ($b=a^5$) and "b:=b*b" ($b=a^{10}$). -Second example: the previous digit was zero. Then we need to -calculate $b^{10}$ which is done by "\apPOWc"~"ppmp", i.e.\ -"\apPOWp\apPOWp\apPOWm\apPOWp", i.e. "b:=b*b;" "b:=b*b", "b:=a*b", "b:=b*b". - -The line~\cite[pow:b1] is equivalent to "a:=b". The non-interleaved format is -extracted from "\OUT" by "\apPOWd" and saved to "\tmpb" and then the "\tmpa" -is set to "\tmpb". - -The second part of "\apPOWb" (lines~\cite[pow:b2] to~\cite[pow:b3]) is equivalent to the -second part of the loop in the algorithm described above. The -multiplication "p:=p*b" is done at lines \cite[pow:b4]~to~\cite[pow:b3]: first the -"\OUT" (i.e.\ the $b$ value) is converted to non-interleaved format by "\apPOWd" and saved to -"\tmpb". This is needed because because "\apMULb" does the multiplication -"\OUT:=\OUT*\tmpb" between interleaved and non-interleaved format (both reversed). -Then the result is ``normalized'' to the initial value of the interleaved format -by the "\apPOWn" macro. All these calculations are processed over "\OUT", -but we set "\OUT:=\tmpc" (i.e.\ the $p$ value) temporary for this multiplication. - -The loop is repeated until the stop-mark "@" is reached. - -\ilabel[pow:b1] {tmpa=} -\ilabel[pow:b2] {apnumE=0} -\ilabel[pow:b3] {OUT=\nb tmpd} -\ilabel[pow:b4] {tmpd=} +The macro \db apPOWb is the body of the loop in the algorithm described above. +The code part after "\ifodd\apnumE" does "p := p*a". In order to do this, we need +to convert "\OUT" (where "a" is stored) into normal format using "\apPOWd". +The result is saved in "\tmpb". Then the multiplication is done by "\apMULd" +and the result is normalized by the "\apPOWn" macro. Because "\apMULd" +works with "\OUT" macro, we temporary set "\tmpc" to "\OUT". +The code part after "\ifnum\apnumE"{\tt\char`<}"0" does "a := a*a" using the "\apPOWt" +macro. The result is normalized by the "\apPOWn" macro. \inext{apPOWb}{^^B\cbrace}{++} -The \db apPOWc "<letters><dot>" does "\apPOW<letter>" "\apPOW<letter>" etc. -For example "\apPOWc ppm." processes "\apPOWp\apPOWp\apPOWm". - -\inext{apPOWc}{}{++} - The macro \db apPOWd "<initialized interleaved reversed format>" extracts the Digits from its argument and saves them to the "\tmpb" macro. @@ -1710,13 +1654,6 @@ It ignores the first two elements from the format and runs \db apPOWh. \inext{apPOWg}{^^B\cbrace}{++} -The macro \db apPOWm does "b:=a*b", i.e.\ "\OUT:=\tmpa*\OUT". The \db apPOWp -does "b:=b*b", i.e.\ "\OUT:=\OUT*\OUT". The ``normalization'' of "\OUT" is -done by the "\apPOWn" macro after the calculation is finished. It means that -the interleaved format is reinitialized. - -\inext{apPOWm}{apPOWp}{++} - The normalization to the initialized interleaved format of the "\OUT" is done by the \db apPOWn "<data>@" macro. The \db apPOWna reads the first part of the "<data>" (to the first "*", where the Digits are non-interleaved. The |