-
Notifications
You must be signed in to change notification settings - Fork 2
/
IntMath.def
166 lines (129 loc) · 6.36 KB
/
IntMath.def
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
(*!m2pim*) (* Copyright (c) 2017 B.Kowarsch. All rights reserved. *)
DEFINITION MODULE IntMath;
(* Integer Math library *)
FROM UnsignedInt IMPORT UINTEGER; (* 0..MAX(INTEGER) *)
(* --------------------------------------------------------------------------
* Integer Division Operations
* --------------------------------------------------------------------------
* There are several different definitions for integer division all of which
* produce different results when at least one of the operands is negative.
* Commonly used variants are truncated, floored and rounded division.
*
* Truncated integer division, defined as
* q = trunc(i/j)
*
* Floored integer division, defined as
* q = floor(i/j)
*
* Rounded integer division, defined as
* q = round(i/j)
*
* The respective definitions of the modulus operation are derived from the
* definitions for integer division to satisfy the division rule (2) of the
* Euclidean theorem:
*
* (1) there exists a whole number q, where
* (2) i = j * q + r, and
* (3) 0 <= r < | j |
*
* In a seminal paper (Boute, 1992), Raymond T. Boute at the University of
* Nijmegen proposed a mathematically more correct and useful definition.
* It is defined to satisfy all three conditions of the Euclidean theorem.
*
* Euclidean integer division, defined as
* i = j * div(i, j) + mod(i, j) and 0 <= mod(i, j) < abs(j)
*
* Different editions of PIM Modula-2 have used variants of truncated and
* floored integer division for DIV and MOD. It is therefore impossible to
* write portable code across different PIM implementations when using DIV
* and MOD where at least one of the operands may be negative.
*
* For portability, this library provides three pairs of div/mod functions.
* o ediv() and emod() following the Euclidean definition
* o fdiv() and fmod() following the floored division definition
* o tdiv() and tmod() following the truncated division definition
*
* for i>=0 and j>0
* ediv(), fdiv() and tdiv() return the same results,
* emod(), fmod() and tmod() return the same results.
*
* for i>=0 and j<0
* ediv() and fdiv() return the same results,
* emod() and fmod() return the same results.
*
* for i<0 and j>0
* ediv() and tdiv() return the same results,
* emod() and tmod() return the same results.
*
* for i<0 and j<0
* fdiv() and tdiv() return the same results,
* fmod() and tmod() return the same results.
*
* [Boute, 1992] Raymond T. Boute, "The Euclidean Definition of the Functions
* div and mod", ACM Transactions on Programming Languages, Vol.14, No.2,
* April, 1992.
* ----------------------------------------------------------------------- *)
(* --------------------------------------------------------------------------
* function ediv(i)
* --------------------------------------------------------------------------
* Returns the quotient q of euclidean division i by j.
* ----------------------------------------------------------------------- *)
PROCEDURE ediv ( i, j : INTEGER ) : INTEGER;
(* --------------------------------------------------------------------------
* function emod(i)
* --------------------------------------------------------------------------
* Returns the remainder r of euclidean division i by j.
* ----------------------------------------------------------------------- *)
PROCEDURE emod ( i, j : INTEGER ) : INTEGER;
(* --------------------------------------------------------------------------
* function fdiv(i)
* --------------------------------------------------------------------------
* Returns the quotient q of floored division i by j.
* ----------------------------------------------------------------------- *)
PROCEDURE fdiv ( i, j : INTEGER ) : INTEGER;
(* --------------------------------------------------------------------------
* function fmod(i)
* --------------------------------------------------------------------------
* Returns the remainder r of floored division i by j.
* ----------------------------------------------------------------------- *)
PROCEDURE fmod ( i, j : INTEGER ) : INTEGER;
(* --------------------------------------------------------------------------
* function tdiv(i)
* --------------------------------------------------------------------------
* Returns the quotient q of truncated division i by j.
* ----------------------------------------------------------------------- *)
PROCEDURE tdiv ( i, j : INTEGER ) : INTEGER;
(* --------------------------------------------------------------------------
* function tmod(i)
* --------------------------------------------------------------------------
* Returns the remainder r of truncated division i by j.
* ----------------------------------------------------------------------- *)
PROCEDURE tmod ( i, j : INTEGER ) : INTEGER;
(* --------------------------------------------------------------------------
* Integer Exponentiation and Logarithm Operations
* ----------------------------------------------------------------------- *)
(* --------------------------------------------------------------------------
* function intPow2(i)
* --------------------------------------------------------------------------
* Returns the power of 2 for argument i
* ----------------------------------------------------------------------- *)
PROCEDURE intPow2 ( i : UINTEGER ) : INTEGER;
(* --------------------------------------------------------------------------
* function intLog2(i)
* --------------------------------------------------------------------------
* Returns the integral part of the logarithm of 2 for argument i
* ----------------------------------------------------------------------- *)
PROCEDURE intLog2 ( i : UINTEGER ) : INTEGER;
(* --------------------------------------------------------------------------
* function intPow10(i)
* --------------------------------------------------------------------------
* Returns the power of 10 for argument i
* ----------------------------------------------------------------------- *)
PROCEDURE intPow10 ( i : UINTEGER ) : INTEGER;
(* --------------------------------------------------------------------------
* function intLog10(i)
* --------------------------------------------------------------------------
* Returns the integral part of the logarithm of 10 for argument i
* ----------------------------------------------------------------------- *)
PROCEDURE intLog10 ( i : UINTEGER ) : INTEGER;
END IntMath.