17

TeX uses scaled point as its minimal unit. At least it's said so in the TeXbook:

TeX represents all dimensions internally as an integer multiple of the tiny units called sp.

65536 sp = 2^{16} sp = 1 pt.

And later on,

TeX actually does its calculations with integer multiples of 2^{-16}...

BUT, compile this and you will see, that 0.00000762939453125 starts to be distinguishable from zero, which means that it's TeX's minimal unit. (0.00000762939453125 is exactly 2^{-17})

\line{\hskip 0pt plus 16383.99999fil and now?\hskip 0pt plus 0.000007629394531249fill}
\line{\hskip 0pt plus 16383.99999fil and now?\hskip 0pt plus 0.000007629394531250fill}
\bye

So, what is the real minimal unit: 2^{-16} or 2^{-17} ?

  • 2
    The real minimal unit is 1sp, period. – Werner Mar 4 '15 at 8:19
  • Really matter? I wonder if anyone would really note the difference of about 0,005 µm (the size of the smallest viruses) in a document :) – Fran Mar 4 '15 at 21:45
  • @Fran "A scaled point is huge, more than two farshimmelt potrzebies; it's more than 53 Angstrom units, 'way bigger than a hydrogen atom." : ) – Igor Liferenko Mar 10 '15 at 9:12
  • I now the TUGboat article :) I understand Donald's concern about that \maxdimen do not reach Sagan's number in meters (for covering a building with a banner, for example) but I do not share his concern for the arrival of the nanotechnology era. Even thinking in VR glasses, I can't visualize the future with nanobooks or miliportzebieposters. – Fran Mar 10 '15 at 12:29
27

When you say

\dimen0=0.00000762939453125pt

a \showthe\dimen0 instruction will answer

> 0.00002pt.

because this is what 1sp looks like when shown in points.

What happens? TeX does binary arithmetic, deep down inside the program. The number you input is recognized as greater than zero (one should look into the program code) and so the dimension is set to the smallest positive one.

Similarly, after

\skip0=0pt plus 0.000007629394531250fill \showthe\skip0

you get

> 0.0pt plus 0.00002fill.

so never is a positive dimension less than 1sp used. The value you input can appear less than 1sp, but the value that TeX uses is 1sp.

The conversion from decimal number to scaled integer is described in module 102 of tex.web; the integral part is just multiplied by 65536, so it's only interesting for numbers in the form 0.d0d1dk–1

The final scaled integer is stored in a which is initialized as 0. Then we start from the far right and at each step a is assigned the result of

(a + di * 217) div 10

Finally, a is assigned the value (a + 1) div 2 (with truncation)

If we carry out this algorithm, we get the following numbers as values of a (in parentheses the digit examined)

(5)  65536
(2)  32768
(1)  16384
(3)  40960
(5)  69632
(4)  59392
(9) 123904
(3)  51712
(9) 123136
(2)  38528
(6)  82496
(7) 100000
(0)  10000
(0)   1000
(0)    100
(0)     10
(0)      1
final step (1+1) div 2 = 1

The div operation works by truncation.

I leave as an exercise to show that 0.0000152587890625 = 2–16 produces 1 as well and that 0.000007629394531249 produces 0 instead.

As you see, the algorithm uses 217 to ensure 16 bit precision of the fractional part.

  • your description is incomplete the final value of a is divided by 2 and rounded by the assignment a<- (a+1)div 2. – user4686 Mar 4 '15 at 13:32
17

When you input a dimension as a certain (positive) decimal number of points, it will be rounded to the nearest integral multiple of 1/65536 pt = 1sp, where numbers from N.5 inclusive to (N+1).5 exclusive are rounded to N+1.

This can be illustrated by the following experiments. They need the e-TeX extensions (compile with pdftex or etex), but I checked that the conclusions are obeyed in Knuth tex.

I also checked mathematically that the specific algorithm described in egreg's answer produces exactly what I am saying here. See below.

% compile with etex or pdftex

\input xintexpr.sty

\tt

\def\Test #1{% #1 = integer
    \def\a {#1/65536}%
    \def\b {(#1+1)/65536}%
    \def\delta {1/65536}%
    This is #1/65536 in decimal: \xinttheiexpr [30]\a \relax.\endgraf
    This is (#1+1)/65536 in decimal: \xinttheiexpr [30]\b \relax.\endgraf
    \def\Iterate {%
        \edef\c {\xinttheiexpr [30](\a+\b)/2\relax }%
        \ifnum\number\dimexpr \c pt\relax >#1
              \let\b\c
        \else
              \let\a\c
        \fi
        \edef\delta {\xinttheexpr \delta/2\relax }%
        }%
    \loop
        \Iterate
        \xintifboolexpr {\delta < 10^(-25)}{\iffalse}{\iftrue}%
    \repeat
    \edef\A {\xinttheiexpr [30]\a*65536\relax}%
    \edef\B {\xinttheiexpr [30]\b*65536\relax}%
    $\a \approx {\A\over 65536}$\endgraf
    $\a$ pt is represented internally as
    $\number\dimexpr \a pt\relax$ (sp).\endgraf
    $\b \approx {\B \over 65536}$\endgraf
    $\b$ pt is represented internally as
    $\number\dimexpr \b pt\relax$ (sp).\endgraf
    \vskip.5cm
}


\Test {0}

\Test {1}

\Test {2}

\Test {3}

\Test {17}

\Test {123456789}

\nopagenumbers
\bye

rounding to scaled points

(update corrects typo in indices)

\documentclass[a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{geometry}
\usepackage{newtxtext,newtxmath}
\let\leq\leqslant
\let\geq\geqslant
\begin{document}\pagestyle{empty}

Let us start from a decimal number $x$ in $[0,1)$ with $k$ digits after
decimal mark.
\[ x = 0.d_k\cdots d_1\]
Enumerating the digits this way facilitates my description next. We set
$a_0=0$ and define repetitively up to $j=k$ the following non-negative integers:
\[ a_{j+1} = \lfloor \frac{a_j + 2^{17}\cdot d_{j+1}}{10}\rfloor \]
Once we reach $a_k$ we do a final definition:
\[ a = \lfloor \frac{a_k+1}2 \rfloor\]
By definition
\[ a_1 \leq \frac{d_1\cdot 2^{17}}{10} < a_1 + 1\]
\[ 10a_1 \leq d_1 \cdot 2^{17} < 10a_1 + 10\]
Because everything in sight is integer valued, we can improve this to:
\[  10a_1 \leq d_1 \cdot 2^{17} \leq 10a_1 + 9\]
Similarly
\[a_2 \leq \frac{a_1 + d_2\cdot 2^{17}}{10} < a_2 + 1\]
\[ 10a_2 \leq a_1 + d_2 \cdot 2^{17} < 10a_2 + 10\]
Again everything in sight is integer valued:
\[ 10 a_2 \leq a_1 + d_2 \cdot 2^{17} \leq 10a_2 +9 = 10a_2 + 10 - 1\]
We transform this into
\[ 10^2 a_2 \leq 10^1 a_1 + 10^1 d_2\cdot 2^{17}\leq 10^2 a_2 + 100 - 10\]
Then, similarly
\[10^3 a_3 \leq 10^2 a_2 + 10^2 d_3\cdot  2^{17}\leq 10^3 a_3 + 10^3 - 10^2\]
\[10^4 a_4 \leq 10^3 a_3 + 10^3 d_4\cdot  2^{17}\leq 10^4 a_4 + 10^4 - 10^3\]
up to
\[10^k a_k \leq 10^{k-1}a_{k-1} + 10^{k-1}d_{k}\cdot 2^{17}\leq 10^k a_k +
10^k - 10^{k-1}\]
If we add up everything and simplify the common terms we end up with 
\[ 10^k a_k\leq (10^{k-1}d_{k}+\cdots + d_1)\cdot 2^{17}\leq 10^k a_k + 10^k
-1\]
Thus
\[ \frac{a_k}2 \leq  2^{16}\cdot x \leq \frac{a_k + 1 - 10^{-k}}2 <
\frac{a_k+1}2\]
If $a_k = 2j$ is even, the rule of \textsc{D.~Knuth} is now to set $a = j$ and
this $j$ satifies
\[ j \leq 2^{16}\cdot x < j + 0.5\]
If $a_k = 2j+1$ is odd, the rule of \textsc{D.~Knuth} is to set $a = j+1$ and
we have
\[ j + 0.5 \leq 2^{16}\cdot x < j +1\]
Hence in all cases we have the formula:
\[ a = \lfloor 2^{16}\cdot x+0.5\rfloor\]
in other words $a$ is the \textbf{rounded} value of $2^{16}\cdot x$.


As originally claimed by your humble servant.


Sincerely,\par
Mercredi 04 mars 2015 à 15:27:34\par
typo corrected Mercredi 04 mars 2015 à 16:01:51

\vskip.2cm
\hrule
\end{document}

first part of proof second part of proof

Let me also add some extra argument to explain why TeX's scanning discards all but the first seventeen digits after decimal mark:

(typo corrected, it was §452 not §402)

addendum to the proof vz §452 of tex.web

To dispel potential confusion recall that the above is only for decimal numbers of the shape 0.abcedf.... Digits before the dot are treated separately, it is only for digits after the dot that only 17 at max need to kept in the process.

  • at jfbu: it does not compile via pdftex - pastebin.com/Y9UBW1RY – Igor Liferenko Mar 4 '15 at 9:43
  • 1
    @IgorLiferenko try updating xint. The \xinttheiexpr [30] thing was introduced in release 1.1 (2014/10/28). – user4686 Mar 4 '15 at 9:49
  • alternatively replace everywhere in the code \xinttheiexpr [30] stuff\relax by \xintRound {30}{\xinttheexpr stuff\relax}. Be careful to use \xinttheexpr and not \xinttheiexpr in this variant. – user4686 Mar 4 '15 at 9:54
  • In this context, and in contrast, TeX truncates, rather than rounding, when an operation on dimensions does not give an integral number of sp. Example: \dimen0 123sp , \divide \dimen0 by 2 , \number\dimen0 returns 61 and more striking \dimen0 129sp , \divide \dimen0 by 10 , \number\dimen0 returns 12. – user4686 Mar 4 '15 at 10:15
  • 1
    @IgorLiferenko No, to tug.org/TUGboat/tb35-1/tb109knut.pdf – egreg Mar 5 '15 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.