Annotation of OpenXM/doc/OpenXM-specs/cmo-basic1.tex, Revision 1.14
1.14 ! noro 1: %% $OpenXM: OpenXM/doc/OpenXM-specs/cmo-basic1.tex,v 1.13 2005/03/04 03:49:47 takayama Exp $
1.1 noro 2: //&jp \section{ 数, 多項式 の CMO 表現 }
3: //&eg \section{ CMOexpressions for numbers and polynomials }
1.4 noro 4: \label{sec:basic1}
1.1 noro 5: /*&C
6: @../SSkan/plugin/cmotag.h
7: \begin{verbatim}
8: #define CMO_MONOMIAL32 19
9: #define CMO_ZZ 20
10: #define CMO_QQ 21
11: #define CMO_ZERO 22
12: #define CMO_DMS_GENERIC 24
13: #define CMO_DMS_OF_N_VARIABLES 25
14: #define CMO_RING_BY_NAME 26
15: #define CMO_DISTRIBUTED_POLYNOMIAL 31
16: #define CMO_RATIONAL 34
1.14 ! noro 17: #define CMO_COMPLEX 35
1.1 noro 18:
19:
20: #define CMO_INDETERMINATE 60
21: #define CMO_TREE 61
22: #define CMO_LAMBDA 62 /* for function definition */
23: \end{verbatim}
24:
25: */
26:
27: /*&jp
1.4 noro 28: 以下, グループ CMObject/Basic, CMObject/Tree
1.1 noro 29: および CMObject/DistributedPolynomial
30: に属する CMObject の形式を説明する.
31:
1.5 noro 32: \noindent
33: {\tt OpenXM/src/ox\_toolkit} にある {\tt bconv} をもちいると
34: CMO expression を binary format に変換できるので,
35: これを参考にするといい.
1.1 noro 36: */
37: /*&eg
38: In the sequel, we will explain on the groups
1.4 noro 39: CMObject/Basic, CMObject/Tree
1.1 noro 40: and CMObject/DistributedPolynomial.
1.5 noro 41:
42: \noindent
43: The program {\tt bconv} at {\tt OpenXM/src/ox\_toolkit}
44: translates
45: CMO expressions into binary formats.
46: It is convinient to understand the binary formats explained in
47: this section.
1.1 noro 48: */
49:
1.5 noro 50: /*&C
51: \noindent Example:
52: \begin{verbatim}
53: bash$ ./bconv
54: > (CMO_ZZ,123123);
55: 00 00 00 14 00 00 00 01 00 01 e0 f3
56: \end{verbatim}
57: */
1.1 noro 58: /*&jp
59:
60: \bigbreak
61: \noindent
1.4 noro 62: Group CMObject/Basic requires CMObject/Primitive. \\
1.12 takayama 63: ZZ, QQ, Zero, Rational, Indeterminate $\in$ CMObject/Basic. \\
1.1 noro 64: \begin{eqnarray*}
65: \mbox{Zero} &:& ({\tt CMO\_ZERO}) \\
66: & & \mbox{ --- ユニバーサルな ゼロを表す. } \\
1.12 takayama 67: \mbox{ZZ} &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots ,
1.9 noro 68: {\sl byte}\, \mbox{a[$|$f$|$]} ) \\
1.1 noro 69: &:& \mbox{ --- bignum をあらわす. a[i] についてはあとで説明}\\
1.9 noro 70: \mbox{QQ} &:& ({\tt CMO\_QQ},
71: {\sl int32}\, {\rm m}, {\sl byte}\, \mbox{a[1]}, \ldots, {\sl byte}\, \mbox{a[$|$m$|$]},
72: {\sl int32}\, {\rm n}, {\sl byte}\, \mbox{b[1]}, \ldots, {\sl byte}\, \mbox{b[$|$n$|$]})\\
1.1 noro 73: & & \mbox{ --- 有理数 $a/b$ を表す. } \\
74: \mbox{Rational} &:& ({\tt CMO\_RATIONAL}, {\sl CMObject}\, {\rm a}, {\sl CMObject}\, {\rm b}) \\
75: & & \mbox{ --- $a/b$ を表す. } \\
1.14 ! noro 76: \mbox{Bigfloat} &:& ({\tt CMO\_BIGFLOAT},
! 77: {\sl int32}\, {\rm sign}, {\sl int32}\, {\rm prec}, {\sl int64}\, {\rm exp},
! 78: {\sl int32}\, \mbox{a[1]}, \ldots , {\sl int32}\, \mbox{a[$\lfloor \frac{{\rm prec}+31}{32} \rfloor$]} ) \\
! 79: &:& \mbox{ --- bigfloat をあらわす. a[i] についてはあとで説明}\\
! 80: \mbox{Complex} &:& ({\tt CMO\_COMPLEX}, {\sl CMObject}\, {\rm re}, {\sl CMObject}\, {\rm im}) \\
! 81: & & \mbox{ --- $a+b\sqrt{-1}$ を表す. } \\
1.1 noro 82: \mbox{Indeterminate} &:& ({\tt CMO\_INDETERMINATE}, {\sl Cstring}\, {\rm v}) \\
83: & & \mbox{ --- 変数名 $v$ . } \\
84: \end{eqnarray*}
85: */
1.12 takayama 86:
87:
1.1 noro 88: /*&eg
89:
90: \bigbreak
91: \noindent
1.4 noro 92: Group CMObject/Basic requires CMObject/Primitive. \\
1.12 takayama 93: ZZ, QQ, Zero, Rational, Indeterminate $\in$ CMObject/Basic. \\
1.1 noro 94: \begin{eqnarray*}
95: \mbox{Zero} &:& ({\tt CMO\_ZERO}) \\
96: & & \mbox{ --- Universal zero } \\
1.12 takayama 97: \mbox{ZZ} &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots ,
1.9 noro 98: {\sl byte}\, \mbox{a[$|$m$|$]} ) \\
1.1 noro 99: &:& \mbox{ --- bignum. The meaning of a[i] will be explained later.}\\
1.9 noro 100: \mbox{QQ} &:& ({\tt CMO\_QQ},
101: {\sl int32}\, {\rm m}, {\sl byte}\, \mbox{a[1]}, \ldots, {\sl byte}\, \mbox{a[$|$m$|$]},
102: {\sl int32}\, {\rm n}, {\sl byte}\, \mbox{b[1]}, \ldots, {\sl byte}\, \mbox{b[$|$n$|$]})\\
1.1 noro 103: & & \mbox{ --- Rational number $a/b$. } \\
104: \mbox{Rational} &:& ({\tt CMO\_RATIONAL}, {\sl CMObject}\, {\rm a}, {\sl CMObject}\, {\rm b}) \\
105: & & \mbox{ --- Rational expression $a/b$. } \\
1.14 ! noro 106: \mbox{Bigfloat} &:& ({\tt CMO\_BIGFLOAT},
! 107: {\sl int32}\, {\rm sign}, {\sl int32}\, {\rm prec}, {\sl int64}\, {\rm exp},
! 108: {\sl int32}\, \mbox{a[1]}, \ldots , {\sl int32}\, \mbox{a[$\lfloor \frac{{\rm prec}+31}{32} \rfloor$]} ) \\
! 109: &:& \mbox{ --- bignfloat. The meaning of a[i] will be explained later.}\\
! 110: \mbox{Complex} &:& ({\tt CMO\_COMPLEX}, {\sl CMObject}\, {\rm re}, {\sl CMObject}\, {\rm im}) \\
! 111: & & \mbox{ --- Complex number $a+b\sqrt{-1}$. } \\
1.1 noro 112: \mbox{Indeterminate} &:& ({\tt CMO\_INDETERMINATE}, {\sl Cstring}\, {\rm v}) \\
113: & & \mbox{ --- Variable name $v$ . } \\
114: \end{eqnarray*}
115: */
116: /*&C
117:
118: */
1.12 takayama 119: /*&C
120:
121: */
1.1 noro 122:
123: /*&jp
124: Indeterminate は変数名をあらわす.
125: v はバイト列であればなにを用いてもよいが,
126: システム毎に変数名として用いられるバイト列は制限がある.
127: 各システム xxx は任意の文字列を各システム固有の変数名へ1対1に変換できるように
128: 実装しないといけない.
129: (これを
130: {\tt Dx} は {\tt \#dx} と変換するなどの
131: escape sequence を用いて実現するのは, 無理があるようである.
132: テーブルを作成する必要があるであろう.)
133: */
134: /*&eg
1.12 takayama 135: The name of a variable should be expressed by using Indeterminate.
1.1 noro 136: v may be any sequence of bytes, but each system has its own
137: restrictions on the names of variables.
138: Indeterminates of CMO and internal variable names must be translated
1.12 takayama 139: in one-to-one correspondence.
1.1 noro 140: */
141:
1.12 takayama 142:
1.1 noro 143: /*&jp
1.12 takayama 144: \subsection{Indeterminate および Tree}
1.1 noro 145:
146: \noindent
1.4 noro 147: Group CMObject/Tree requires CMObject/Basic. \\
1.12 takayama 148: Tree, Lambda $\in$ CMObject/Tree. \\
1.1 noro 149: \begin{eqnarray*}
150: \mbox{Tree} &:& ({\tt CMO\_TREE}, {\sl Cstring}\, {\rm name},
1.11 takayama 151: {\sl List}\, {\rm attributes}, {\sl List}\, {\rm leaves}) \\
1.1 noro 152: & & \mbox{ --- 名前 name の定数または関数. 関数の評価はおこなわない. } \\
1.11 takayama 153: & & \mbox{ --- attributes は空リストでなければ name の属性を保持している. }\\
154: & & \mbox{ --- 属性リストは, key と 値のペアである. }\\
1.1 noro 155: \mbox{Lambda} &:& ({\tt CMO\_LAMBDA}, {\sl List}\, {\rm args},
156: {\sl Tree} {\rm body}) \\
157: & & \mbox{ --- body を args を引数とする関数とする. } \\
158: \end{eqnarray*}
159: */
160: /*&eg
1.12 takayama 161: \subsection{Indeterminate and Tree}
1.1 noro 162:
163: \noindent
1.4 noro 164: Group CMObject/Tree requires CMObject/Basic. \\
1.12 takayama 165: Tree, Lambda $\in$ CMObject/Tree. \\
1.1 noro 166: \begin{eqnarray*}
167: \mbox{Tree} &:& ({\tt CMO\_TREE}, {\sl Cstring}\, {\rm name},
1.11 takayama 168: {\sl List}\, {\rm attributes}, {\sl List}\, {\rm leaves}) \\
1.12 takayama 169: & & \mbox{ --- ``name'' is the name of the node of the tree. } \\
170: & & \mbox{ --- Attributes may be a null list. If it is not null, it is a list of}\\
1.11 takayama 171: & & \mbox{ --- key and value pairs. } \\
1.1 noro 172: \mbox{Lambda} &:& ({\tt CMO\_LAMBDA}, {\sl List}\, {\rm args},
173: {\sl Tree} {\rm body}) \\
174: & & \mbox{ --- a function with the arguments body. } \\
175: \end{eqnarray*}
176: */
177:
178: /*&jp
179: 数式を処理するシステムでは, Tree 構造が一般にもちいられる.
180: たとえば, $\sin(x+e)$ は,
181: {\tt (sin, (plus, x, e))}
182: なる Tree であらわすのが一般的である.
183: Tree の表現を スタックマシンのレベルでおこなうとすると,
184: {\tt ox\_BEGIN\_BLOCK}, {\tt ox\_END\_BLOCK} で評価を抑制するのが
185: 一つの方法である (cf. Postscript の {\tt \{ }, {\tt \} }).
186: たとえば上の方法では
187: {\tt x, e, plus, sin } を begin block, end block でかこめばよろしい.
188: われわれはスタックマシンの実装をなるべく簡単にするという立場をとりたい,
189: また数学オブジェクトを OX スタックマシンと CMObject を混在して表現したく
190: ない.
191: したがって,
192: Tree 構造は Open Math 風の表現をもちいた CMO を導入することにした.
193: またこのほうが, われわれの想定するシステム xxx において, Open XM 対応が
194: はるかに容易である.
195: なお, Tree は, Open Math では, Symbol, Application のメカニズムに相当する.
196: */
197: /*&eg
198: In many computer algebra systems, mathematical expressions are usually
199: expressed in terms of a tree structure.
200: For example,
201: $\sin(x+e)$ is expressed as
202: {\tt (sin, (plus, x, e))}
203: as a tree.
1.4 noro 204: Tree may be expressed by putting the expression between
1.3 noro 205: {\tt SM\_beginBlock} and {\tt SM\_endBlock}, which are
206: stack machine commands for delayed evaluation.
207: (cf. {\tt \{ }, {\tt \} } in PostScript).
208: However it makes the implementation of stack machines complicated.
209: It is desirable that CMObject is independent of OX stack machine.
210: Therefore we introduce an OpenMath like tree representation for CMO
1.7 noro 211: Tree object.
1.3 noro 212: This method allows us to implement tree structure easily
213: on individual OpenXM systems.
214: Note that CMO Tree corresponds to Symbol and Application in OpenMath.
1.1 noro 215: */
216:
217:
218: /*&C
219:
220: */
221: /*&jp
222: Lambda は関数を定義するための関数である.
223: Lisp の Lambda 表現と同じ.
1.3 noro 224: */
225: /*&eg
226: Lambda is used to define functions.
1.12 takayama 227: The notion ``lambda'' is borrowed from the language Lisp.
1.3 noro 228: */
1.1 noro 229:
230: \noindent
1.3 noro 231: //&jp 例: $sin(x+e)$ の表現.
232: //&eg Example: the expression of $sin(x+e)$.
1.1 noro 233: \begin{verbatim}
1.11 takayama 234: (CMO_TREE, (CMO_STRING, "sin"),
235: (CMO_LIST,[size=]1,(CMO_LIST,[size=]2,(CMO_STRING, "cdname"),
236: (CMO_STRING,"basic")))
1.1 noro 237: (CMO_LIST,[size=]1,
238: (CMO_TREE, (CMO_STRING, "plus"), (CMO_STRING, "basic"),
239: (CMO_LIST,[size=]2, (CMO_INDETERMINATE,"x"),
1.6 noro 240: //&jp (CMO_TREE,(CMO_STRING, "e"), 自然対数の底
241: //&eg (CMO_TREE,(CMO_STRING, "e"), the base of natural logarithms
1.12 takayama 242: (CMO_LIST,[size=]1,(CMO_LIST,[size=]2,(CMO_STRING, "cdname"),
243: (CMO_STRING,"basic")))
1.1 noro 244: ))
245: )
246: )
247: \end{verbatim}
1.10 takayama 248: //&jp Leave の成分には, 多項式を含む任意のオブジェクトがきてよい.
249: //&eg Elements of the leave may be any objects including polynomials.
1.1 noro 250:
251: \noindent
252: Example:
253: \begin{verbatim}
1.12 takayama 254: sm1> [(plus) [[(cdname) (basic)]] [(123).. (345)..]] [(class) (tree)] dc ::
255: Class.tree [$plus$ , [[$cdname$ , $basic$ ]], [ 123 , 345 ] ]
1.1 noro 256: \end{verbatim}
257:
1.12 takayama 258: \noindent
259: Example:
260: \begin{verbatim}
261: asir
262: [753] taka_cmo100_xml_form(quote(sin(x+1)));
263: <cmo_tree> <cmo_string>"sin"</cmo_string>
264: <cmo_list><cmo_int32 for="length">1</cmo_int32>
265: <cmo_list><cmo_int32 for="length">2</cmo_int32>
266: <cmo_string>"cdname"</cmo_string>
267: <cmo_string>"basic"</cmo_string>
268: </cmo_list> </cmo_list>
269: <cmo_tree> <cmo_string>"plus"</cmo_string>
270: <cmo_list><cmo_int32 for="length">1</cmo_int32>
271: <cmo_list><cmo_int32 for="length">2</cmo_int32>
272: <cmo_string>"cdname"</cmo_string>
273: <cmo_string>"basic"</cmo_string>
274: </cmo_list> </cmo_list>
275: <cmo_indeterminate> <cmo_string>"x"</cmo_string> </cmo_indeterminate>
276: <cmo_zz>1</cmo_zz>
277: </cmo_tree></cmo_tree>
278: \end{verbatim}
1.1 noro 279:
280:
281: \bigbreak
1.3 noro 282: //&jp 次に, 分散表現多項式に関係するグループを定義しよう.
1.4 noro 283: /*&eg
1.12 takayama 284: Let us define a group for distributed polynomials. In the following,
1.4 noro 285: DMS stands for Distributed Monomial System.
286: */
1.1 noro 287:
288: \medbreak
289: \noindent
1.4 noro 290: Group CMObject/DistributedPolynomials requires CMObject/Primitive,
291: CMObject/Basic. \\
1.1 noro 292: Monomial, Monomial32, Coefficient, Dpolynomial, DringDefinition,
293: Generic DMS ring, RingByName, DMS of N variables $\in$
294: CMObject/DistributedPolynomials. \\
1.3 noro 295: /*&jp
1.1 noro 296: \begin{eqnarray*}
297: \mbox{Monomial} &:& \mbox{Monomial32}\, |\, \mbox{Zero} \\
298: \mbox{Monomial32}&:& ({\tt CMO\_MONOMIAL32}, {\sl int32}\, n,
299: {\sl int32}\, \mbox{e[1]}, \ldots,
300: {\sl int32}\, \mbox{e[n]}, \\
301: & & \ \mbox{Coefficient}) \\
302: & & \mbox{ --- e[i] で, $n$ 変数 monomial
303: $x^e = x_1^{e_1} \cdots x_n^{e_n}$ の各指数 $e_i$
304: をあらわす.} \\
305: \mbox{Coefficient}&:& \mbox{ZZ} | \mbox{Integer32} \\
306: \mbox{Dpolynomial}&:& \mbox{Zero} \\
1.12 takayama 307: & & |\ ({\tt CMO\_DISTRIBUTED\_POLYNOMIAL},{\sl int32}\, m, \\
1.1 noro 308: & & \ \ \mbox{DringDefinition},
309: [\mbox{Monomial32}|\mbox{Zero}], \\
310: & &\ \
311: \{\mbox{Monomial32}\}) \\
312: & &\mbox{--- m はモノミアルの個数である.}\\
313: \mbox{DringDefinition}
314: &:& \mbox{DMS of N variables} \\
315: & & |\ \mbox{RingByName} \\
316: & & |\ \mbox{Generic DMS ring} \\
317: & & \mbox{ --- 分散表現多項式環の定義. } \\
318: \mbox{Generic DMS ring}
1.2 noro 319: &:& \mbox{({\tt CMO\_DMS\_GENERIC}) --- 新版はこちら}\\
1.1 noro 320: \mbox{RingByName}&:& ({\tt CMO\_RING\_BY\_NAME}, {\sl Cstring}\ {\rm s}) \\
321: & & \mbox{ --- 名前 s で, 格納された ring 定義.} \\
322: \mbox{DMS of N variables}
323: &:& ({\tt CMO\_DMS\_OF\_N\_VARIABLES}, \\
324: & & \ ({\tt CMO\_LIST}, {\sl int32}\, \mbox{m},
325: {\sl Integer32}\, \mbox{n}, {\sl Integer32}\,\mbox{p} \\
326: & & \ \ [,{\sl object}\,\mbox{s}, {\sl Cstring}\,\mbox{c},
327: {\sl List}\, \mbox{vlist},
328: {\sl List}\, \mbox{wvec}, {\sl List}\, \mbox{outord}]) \\
329: & & \mbox{ --- m はあとに続く要素の数} \\
330: & & \mbox{ --- n は変数の数, p は 標数} \\
331: & & \mbox{ --- s は ring の名前} \\
332: & & \mbox{ --- c は係数環, QQ, ZZ の場合は文字列で QQ, ZZ と書く.} \\
333: & & \mbox{ --- vlist は Indeterminate のリスト(新版). 多項式環の変数リスト} \\
334: & & \mbox{ --- wvec は order をきめる weight vector,} \\
335: & & \mbox{ --- outord は出力するときの変数順序.} \\
336: \end{eqnarray*}
1.3 noro 337: */
338: /*&eg
339: \begin{eqnarray*}
340: \mbox{Monomial} &:& \mbox{Monomial32}\, |\, \mbox{Zero} \\
341: \mbox{Monomial32}&:& ({\tt CMO\_MONOMIAL32}, {\sl int32}\, n,
342: {\sl int32}\, \mbox{e[1]}, \ldots,
343: {\sl int32}\, \mbox{e[n]}, \\
344: & & \ \mbox{Coefficient}) \\
345: & & \mbox{ --- e[i] is the exponent $e_i$ of the monomial
346: $x^e = x_1^{e_1} \cdots x_n^{e_n}$. } \\
347: \mbox{Coefficient}&:& \mbox{ZZ} | \mbox{Integer32} \\
348: \mbox{Dpolynomial}&:& \mbox{Zero} \\
1.12 takayama 349: & & |\ ({\tt CMO\_DISTRIBUTED\_POLYNOMIAL},{\sl int32}\, m, \\
1.3 noro 350: & & \ \ \mbox{DringDefinition}, [\mbox{Monomial32}|\mbox{Zero}], \\
351: & &\ \
352: \{\mbox{Monomial32}\}) \\
353: & &\mbox{--- m is equal to the number of monomials.}\\
354: \mbox{DringDefinition}
355: &:& \mbox{DMS of N variables} \\
356: & & |\ \mbox{RingByName} \\
357: & & |\ \mbox{Generic DMS ring} \\
358: & & \mbox{ --- definition of the ring of distributed polynomials. } \\
359: \mbox{Generic DMS ring}
360: &:& ({\tt CMO\_DMS\_GENERIC}) \\
361: \mbox{RingByName}&:& ({\tt CMO\_RING\_BY\_NAME}, {\sl Cstring} s) \\
1.4 noro 362: & & \mbox{ --- The ring definition referred by the name ``s''.} \\
1.3 noro 363: \mbox{DMS of N variables}
364: &:& ({\tt CMO\_DMS\_OF\_N\_VARIABLES}, \\
365: & & \ ({\tt CMO\_LIST}, {\sl int32}\, \mbox{m},
366: {\sl Integer32}\, \mbox{n}, {\sl Integer32}\, \mbox{p} \\
367: & & \ \ [,{\sl Cstring}\,\mbox{s}, {\sl List}\, \mbox{vlist},
368: {\sl List}\, \mbox{wvec}, {\sl List}\, \mbox{outord}]) \\
369: & & \mbox{ --- m is the number of elements.} \\
370: & & \mbox{ --- n is the number of variables, p is the characteristic} \\
371: & & \mbox{ --- s is the name of the ring, vlist is the list of variables.} \\
372: & & \mbox{ --- wvec is the weight vector.} \\
373: & & \mbox{ --- outord is the order of variables to output.} \\
374: \end{eqnarray*}
375: */
1.1 noro 376:
1.3 noro 377: /*&jp
1.1 noro 378: RingByName や DMS of N variables はなくても, DMS を定義できる.
379: したがって, これらを実装してないシステムで DMS を扱うものが
380: あってもかまわない.
381:
382: 以下, 以上の CMObject にたいする,
383: xxx = asir, kan の振舞いを記述する.
1.3 noro 384: */
385: /*&eg
386: Note that it is possible to define DMS without RingByName and
387: DMS of N variables.
388:
389: In the following we describe how the above CMObjects
390: are implemented on Asir and Kan.
391: */
1.1 noro 392:
393: \subsection{ Zero}
1.3 noro 394: /*&jp
1.12 takayama 395: CMO では ゼロの表現法がなんとおりもあることに注意.
396: %% どのようなゼロをうけとっても,
397: %% システムのゼロに変換できるべきである.
1.3 noro 398: */
399: /*&eg
1.12 takayama 400: Note that CMO has various representations of zero.
1.3 noro 401: */
1.1 noro 402:
403:
1.3 noro 404: //&jp \subsection{ 整数 ZZ }
405: //&eg \subsection{ Integer ZZ }
1.1 noro 406:
407: \begin{verbatim}
408: #define CMO_ZZ 20
409: \end{verbatim}
410:
1.3 noro 411: /*&jp
412: この節ではOpen xxx 規約における任意の大きさの整数(bignum)の扱いについ
413: て説明する. Open XM 規約における多重精度整数を表すデータ型 CMO\_ZZ は
414: GNU MPライブラリなどを参考にして設計されていて, 符号付き絶対値表現を用
415: いている. (cf. {\tt kan/sm1} の配布ディレクトリのなかの {\tt
416: plugin/cmo-gmp.c}) CMO\_ZZ は次の形式をとる.
417: */
418: /*&eg
1.12 takayama 419: We describe the bignum (multi-precision integer) representation
420: {\tt CMO\_ZZ} in OpenXM.
421: The format is similar
1.3 noro 422: to that in GNU MP. (cf. {\tt plugin/cmo-gmp.c} in the {\tt kan/sm1}
423: distribution). CMO\_ZZ is defined as follows.
424: */
1.1 noro 425:
426: \begin{tabular}{|c|c|c|c|c|}
427: \hline
428: {\tt int32 CMO\_ZZ} & {\tt int32 $f$} & {\tt int32 $b_0$} & $\cdots$ &
429: {\tt int32 $b_{n}$} \\
430: \hline
1.3 noro 431: \end{tabular}
432:
433: /*&jp
434: $f$ は32bit整数である. $b_0, \ldots, b_n$ は unsigned int32 である.
435: $|f|$ は $n+1$ である. この CMO の符号は $f$ の符号で定める. 前述し
436: たように, 32bit整数の負数は 2 の補数表現で表される.
437:
438: Open xxx 規約では上の CMO は以下の整数を意味する. ($R = 2^{32}$)
439: */
440: /*&eg
441: $f$ is a 32bit integer. $b_0, \ldots, b_n$ are unsigned 32bit integers.
442: $|f|$ is equal to $n+1$.
1.12 takayama 443: The sign of $f$ represents that of the above integer to be expressed.
444: As stated in Section
1.3 noro 445: \ref{sec:basic0}, a negative 32bit integer is represented by
446: two's complement.
447:
448: In OpenXM the above CMO represents the following integer. ($R = 2^{32}$.)
449: */
1.1 noro 450:
451: \[
452: \mbox{sgn}(f)\times (b_0 R^{0}+ b_1 R^{1} + \cdots + b_{n-1}R^{n-1} + b_n R^n).
453: \]
1.3 noro 454:
455: /*&jp
1.12 takayama 456: \noindent 例:
1.3 noro 457: {\tt int32} を network byte order で表現
458: しているとすると,例えば, 整数 $14$ は CMO\_ZZ で表わすと,
459: */
460: /*&eg
1.12 takayama 461: \noindent Example:
1.3 noro 462: If we express {\tt int32} by the network byte order,
463: a CMO\_ZZ $14$ is expressed by
464: */
1.1 noro 465: \[
466: \mbox{(CMO\_ZZ, 1, 0, 0, 0, e)},
467: \]
1.3 noro 468: //&jp と表わす. これはバイト列では
1.4 noro 469: //&eg The corresponding byte sequence is
1.1 noro 470: \[
471: \mbox{\tt 00 00 00 14 00 00 00 01 00 00 00 0e}
472: \]
1.3 noro 473: //&jp となる.
1.1 noro 474:
475:
1.3 noro 476: //&jp なお ZZ の 0 ( (ZZ) 0 と書く ) は, {\tt (CMO\_ZZ, 00,00,00,00)} と表現する.
477: //&eg Note that CMO\_ZZ 0 is expressed by {\tt (CMO\_ZZ, 00,00,00,00)}.
1.1 noro 478:
479:
1.3 noro 480: //&jp \subsection{ 分散表現多項式 Dpolynomial }
481: //&eg \subsection{ Distributed polynomial Dpolynomial }
1.1 noro 482:
1.3 noro 483: /*&jp
1.1 noro 484: 環とそれに属する多項式は次のような考えかたであつかう.
485:
486: Generic DMS ring に属する元は,
487: 変数を $n$ 個持つ 適当な係数集合 $K$ を持つ多項式環 $K[x_1, \ldots, x_n]$
488: の元である.
489: 係数集合 $K$ がなにかは, 実際データを読み込み, Coefficient を見た段階で
490: わかる.
491: この環に属する多項式を CMO 形式でうけとった場合, 各サーバはその
492: サーバの対応する Object に変換しないといけない.
493: この変換の仕方は, 各サーバ毎にきめる.
494:
495: Asir の場合は, $K[x_1, \ldots, x_n]$ の元は分散表現多項式に変換される.
496: \noroa{ でも, order はどうなるの? }
497:
498: {\tt kan/sm1} の場合は事情は複雑である.
499: {\tt kan/sm1} は, Generic DMS ring にあたる クラスをもたない.
500: つまり, Default で存在する, $n$ 変数の分散表現多項式環は存在しないわけである.
501: したがって, {\tt kan/sm1} では, DMS of N variables が来た場合,
502: これを CurrentRing の元として読み込む. CurrentRing の変数の数が $n'$
503: で, $n' < n$ だと新しい多項式環を生成してデータを読み込む.
504: Order その他の optional 情報はすべて無視する.
505:
506: DMS の 2 番目のフィールドで,
507: Ring by Name を用いた場合, 現在の名前空間で変数 yyy に格納された ring object
508: の元として, この多項式を変換しなさいという意味になる.
509: {\tt kan/sm1} の場合, 環の定義は ring object として格納されており,
510: この ring object を 変数 yyy で参照することにより CMO としてうけとった
511: 多項式をこの ring の元として格納できる.
1.3 noro 512: */
1.1 noro 513:
1.3 noro 514: /*&eg
515: We treat polynomial rings and their elements as follows.
1.1 noro 516:
1.4 noro 517: Generic DMS ring is an $n$-variate polynomial ring $K[x_1, \ldots, x_n]$,
1.12 takayama 518: where $K$ is a coefficient set. $K$ is unknown in advance
1.4 noro 519: and it is determined when coefficients of an element are received.
520: When a server has received an element in Generic DMS ring,
1.3 noro 521: the server has to translate it into the corresponding local object
522: on the server. Each server has its own translation scheme.
523: In Asir such an element are translated into a distributed polynomial.
524: In {\tt kan/sm1} things are complicated.
1.4 noro 525: {\tt kan/sm1} does not have any class corresponding to Generic DMS ring.
1.3 noro 526: {\tt kan/sm1} translates a DMS of N variables into an element of
527: the CurrentRing.
528: If the CurrentRing is $n'$-variate and $n' < n$, then
1.12 takayama 529: an $n$-variate polynomial ring is newly created.
530:
1.3 noro 531:
1.4 noro 532: If RingByName ({\tt CMO\_RING\_BY\_NAME}, yyy)
1.3 noro 533: is specified as the second field of DMS,
534: it requests a sever to use a ring object whose name is yyy
535: as the destination ring for the translation.
536: */
1.1 noro 537:
538: \medbreak \noindent
1.3 noro 539: //&jp {\bf Example}: (すべての数の表記は 16 進表記)
540: //&eg {\bf Example}: (all numbers are represented in hexadecimal notation)
1.1 noro 541: {\footnotesize \begin{verbatim}
542: Z/11Z [6 variables]
543: (kxx/cmotest.sm1) run
544: [(x,y) ring_of_polynomials ( ) elimination_order 11 ] define_ring ;
545: (3x^2 y). cmo /ff set ;
546: [(cmoLispLike) 1] extension ;
547: ff ::
548: Class.CMO CMO StandardEncoding: size = 52, size/sizeof(int) = 13,
549: tag=CMO_DISTRIBUTED_POLYNOMIAL
550:
551: 0 0 0 1f 0 0 0 1 0 0 0 18 0 0 0 13 0 0 0 6
552: 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 1
553: 0 0 0 0 0 0 0 2 0 0 0 3
554:
555: ff omc ::
556: (CMO_DISTRIBUTED_POLYNOMIAL[1f],[size=]1,(CMO_DMS_GENERIC[18],),
557: (CMO_MONOMIAL32[13],3*x^2*y),),
558: \end{verbatim} }
1.3 noro 559: /*&jp
560: $ 3 x^2 y$ は 6 変数の多項式環の 元としてみなされている.
561: */
562: /*&eg
563: $3 x^2 y$ is regarded as an element of a six-variate polynomial ring.
564: */
1.1 noro 565:
566:
1.3 noro 567: //&jp \subsection{再帰表現多項式の定義}
568: //&eg \subsection{Recursive polynomials}
1.1 noro 569:
570: \begin{verbatim}
571: #define CMO_RECURSIVE_POLYNOMIAL 27
572: #define CMO_POLYNOMIAL_IN_ONE_VARIABLE 33
573: \end{verbatim}
574:
1.4 noro 575: Group CMObject/RecursivePolynomial requires CMObject/Primitive, CMObject/Basic.\\
1.1 noro 576: Polynomial in 1 variable, Coefficient, Name of the main variable,
577: Recursive Polynomial, Ring definition for recursive polynomials
578: $\in$ CMObject/RecursivePolynomial \\
579:
1.3 noro 580: /*&jp
1.1 noro 581: \begin{eqnarray*}
582: \mbox{Polynomial in 1 variable} &:&
583: \mbox{({\tt CMO\_POLYNOMIAL\_IN\_ONE\_VARIABLE},\, {\sl int32}\, m, } \\
584: & & \quad \mbox{ Name of the main variable }, \\
1.12 takayama 585: & & \quad \mbox{ \{ {\sl int32} e, Coefficient \}} ) \\
1.1 noro 586: & & \mbox{ --- m はモノミアルの個数. } \\
587: & & \mbox{ --- e, Coefficieint はモノミアルを表現している. } \\
588: & & \mbox{ --- 順序の高い順にならべる. 普通は巾の高い順.} \\
589: & & \mbox{ --- e は 1変数多項式の巾をあらわす. } \\
590: \mbox{Coefficient} &:& \mbox{ ZZ} \,|\, \mbox{ QQ } \,|\,
591: \mbox{ integer32 } \,|\,
592: \mbox{ Polynomial in 1 variable } \\
593: & & \quad \,|\, \mbox{Tree} \,|\, \mbox{Zero} \,|\,\mbox{Dpolynomial}\\
594: \mbox{Name of the main variable } &:&
595: \mbox{ {\sl int32} v } \\
596: & & \mbox{ --- v は 変数番号 (0 からはじまる) を表す. } \\
597: \mbox{Recursive Polynomial} &:&
598: \mbox{ ( {\tt CMO\_RECURSIVE\_POLYNOMIAL}, } \\
1.3 noro 599: & & \quad \mbox{ RringDefinition, } \\
1.1 noro 600: & & \quad
1.12 takayama 601: \mbox{ Polynomial in 1 variable}\, | \, \mbox{Coefficient} ) \\
1.3 noro 602: \mbox{RringDefinition}
1.1 noro 603: & : & \mbox{ {\sl List} v } \\
1.10 takayama 604: & & \quad \mbox{ --- v は, 変数名(indeterminate) または Tree のリスト. } \\
1.1 noro 605: & & \quad \mbox{ --- 順序の高い順. } \\
606: \end{eqnarray*}
1.3 noro 607: */
608: /*&eg
609: \begin{eqnarray*}
610: \mbox{Polynomial in 1 variable} &:&
611: \mbox{({\tt CMO\_POLYNOMIAL\_IN\_ONE\_VARIABLE},\, {\sl int32}\, m, } \\
612: & & \quad \mbox{ Name of the main variable }, \\
1.12 takayama 613: & & \quad \mbox{ \{ {\sl int32} e, Coefficient \}} ) \\
1.4 noro 614: & & \mbox{ --- m is the number of monomials. } \\
615: & & \mbox{ --- A pair of e and Coefficient represents a monomial. } \\
1.3 noro 616: & & \mbox{ --- The pairs of e and Coefficient are sorted in the } \\
617: & & \mbox{ \quad decreasing order, usually with respect to e.} \\
618: & & \mbox{ --- e denotes an exponent of a monomial with respect to } \\
619: & & \mbox{ \quad the main variable. } \\
620: \mbox{Coefficient} &:& \mbox{ ZZ} \,|\, \mbox{ QQ } \,|\,
621: \mbox{ integer32 } \,|\,
622: \mbox{ Polynomial in 1 variable } \\
623: & & \quad \,|\, \mbox{Tree} \,|\, \mbox{Zero} \,|\,\mbox{Dpolynomial}\\
624: \mbox{Name of the main variable } &:&
625: \mbox{ {\sl int32} v } \\
626: & & \mbox{ --- v denotes a variable number. } \\
627: \mbox{Recursive Polynomial} &:&
628: \mbox{ ( {\tt CMO\_RECURSIVE\_POLYNOMIAL}, } \\
629: & & \quad \mbox{ RringDefinition, } \\
630: & & \quad
1.12 takayama 631: \mbox{ Polynomial in 1 variable}\, | \, \mbox{Coefficient} ) \\
1.3 noro 632: \mbox{RringDefinition}
633: & : & \mbox{ {\sl List} v } \\
1.10 takayama 634: & & \quad \mbox{ --- v is a list of names of indeterminates or trees. } \\
1.3 noro 635: & & \quad \mbox{ --- It is sorted in the decreasing order. } \\
636: \end{eqnarray*}
637: */
1.1 noro 638: \bigbreak
639: \noindent
1.3 noro 640: Example:
1.1 noro 641: \begin{verbatim}
642: (CMO_RECURSIEVE_POLYNOMIAL, ("x","y"),
643: (CMO_POLYNOMIAL_IN_ONE_VARIABLE, 2, 0, <--- "x"
644: 3, (CMO_POLYNOMIAL_IN_ONE_VARIABLE, 2, 1, <--- "y"
645: 5, 1234,
646: 0, 17),
647: 1, (CMO_POLYNOMIAL_IN_ONE_VARIABLE, 2, 1, <--- "y"
648: 10, 1,
649: 5, 31)))
650: \end{verbatim}
1.3 noro 651: //&jp これは,
652: //&eg This represents
653: $$ x^3 (1234 y^5 + 17 ) + x^1 (y^{10} + 31 y^5) $$
654: /*&jp
1.1 noro 655: をあらわす.
1.12 takayama 656: %%非可換多項式もこの形式であらわしたいので, 積の順序を上のように
657: %%すること. つまり, 主変数かける係数の順番.
1.3 noro 658: */
659: /*&eg
1.12 takayama 660: %%We intend to represent non-commutative polynomials with the
661: %%same form. In such a case, the order of products are defined
662: %%as above, that is a power of the main variable $\times$ a coeffcient.
663:
1.3 noro 664: */
1.1 noro 665:
666: \noindent
667: \begin{verbatim}
668: sm1
669: sm1>(x^2-h). [(class) (recursivePolynomial)] dc /ff set ;
670: sm1>ff ::
671: Class.recursivePolynomial h * ((-1)) + (x^2 * (1))
672: \end{verbatim}
673:
1.3 noro 674: //&jp \subsection{CPU依存の double }
675: //&eg \subsection{CPU dependent double}
1.1 noro 676:
677: \begin{verbatim}
678: #define CMO_64BIT_MACHINE_DOUBLE 40
679: #define CMO_ARRAY_OF_64BIT_MACHINE_DOUBLE 41
680: #define CMO_128BIT_MACHINE_DOUBLE 42
681: #define CMO_ARRAY_OF_128BIT_MACHINE_DOUBLE 43
682: \end{verbatim}
683:
684: \noindent
1.4 noro 685: Group CMObject/MachineDouble requires CMObject/Primitive.\\
1.1 noro 686: 64bit machine double, Array of 64bit machine double
687: 128bit machine double, Array of 128bit machine double
688: $\in$ CMObject/MachineDouble \\
689:
1.3 noro 690: /*&jp
1.1 noro 691: \begin{eqnarray*}
692: \mbox{64bit machine double} &:&
693: \mbox{({\tt CMO\_64BIT\_MACHINE\_DOUBLE}, } \\
1.12 takayama 694: & & \quad \mbox{ {\sl byte} s1 , \ldots , {\sl byte} s8})\\
1.1 noro 695: & & \mbox{ --- s1, $\ldots$, s8 は {\tt double} (64bit). } \\
696: & & \mbox{ --- この表現はCPU依存である.}\\
1.13 takayama 697: && \mbox{\quad\quad byte order negotiation を用いる.} \\
1.1 noro 698: \mbox{Array of 64bit machine double} &:&
699: \mbox{({\tt CMO\_ARRAY\_OF\_64BIT\_MACHINE\_DOUBLE}, {\sl int32} m, } \\
700: & & \quad \mbox{ {\sl byte} s1[1] , \ldots , {\sl byte}}\, s8[1], \ldots , {\sl byte}\, s8[m])\\
701: & & \mbox{ --- s*[1], $\ldots$ s*[m] は m 個の double (64bit) である. } \\
702: & & \mbox{ --- この表現はCPU依存である.}\\
1.13 takayama 703: & & \mbox{ \quad\quad byte order negotiation を用いる.} \\
1.1 noro 704: \mbox{128bit machine double} &:&
705: \mbox{({\tt CMO\_128BIT\_MACHINE\_DOUBLE}, } \\
1.12 takayama 706: & & \quad \mbox{ {\sl byte} s1 , \ldots , {\sl byte} s16})\\
1.1 noro 707: & & \mbox{ --- s1, $\ldots$, s16 は {\tt long double} (128bit). } \\
708: & & \mbox{ --- この表現はCPU依存である.}\\
1.13 takayama 709: && \mbox{\quad\quad byte order negotiation を用いる.} \\
1.1 noro 710: \mbox{Array of 128bit machine double} &:&
711: \mbox{({\tt CMO\_ARRAY\_OF\_128BIT\_MACHINE\_DOUBLE}, {\sl int32} m, } \\
1.12 takayama 712: & & \quad \mbox{ {\sl byte} s1[1] , \ldots , {\sl byte} s16[1], \ldots , {\sl byte} s16[m]})\\
1.1 noro 713: & & \mbox{ --- s*[1], $\ldots$ s*[m] は m 個の long double (128bit) である. } \\
714: & & \mbox{ --- この表現はCPU依存である.}\\
1.13 takayama 715: & & \mbox{ \quad\quad byte order negotiation を用いる.}
1.1 noro 716: \end{eqnarray*}
1.3 noro 717: */
718: /*&eg
719: \begin{eqnarray*}
720: \mbox{64bit machine double} &:&
721: \mbox{({\tt CMO\_64BIT\_MACHINE\_DOUBLE}, } \\
1.12 takayama 722: & & \quad \mbox{ {\sl byte} s1 , \ldots , {\sl byte} s8})\\
1.3 noro 723: & & \mbox{ --- s1, $\ldots$, s8 は {\tt double} (64bit). } \\
1.12 takayama 724: & & \mbox{ --- Encoding depends on CPU.}\\
1.13 takayama 725: && \mbox{\quad\quad Need the byte order negotiation.} \\
1.3 noro 726: \mbox{Array of 64bit machine double} &:&
727: \mbox{({\tt CMO\_ARRAY\_OF\_64BIT\_MACHINE\_DOUBLE}, {\sl int32} m, } \\
728: & & \quad \mbox{ {\sl byte} s1[1] , \ldots , {\sl byte}}\, s8[1], \ldots , {\sl byte}\, s8[m])\\
729: & & \mbox{ --- s*[1], $\ldots$ s*[m] are 64bit double's. } \\
1.12 takayama 730: & & \mbox{ --- Encoding depends on CPU.}\\
1.13 takayama 731: & & \mbox{\quad\quad Need the byte order negotiation.} \\
1.3 noro 732: \mbox{128bit machine double} &:&
733: \mbox{({\tt CMO\_128BIT\_MACHINE\_DOUBLE}, } \\
1.12 takayama 734: & & \quad \mbox{ {\sl byte} s1 , \ldots , {\sl byte} s16})\\
1.3 noro 735: & & \mbox{ --- s1, $\ldots$, s16 は {\tt long double} (128bit). } \\
1.12 takayama 736: & & \mbox{ --- Encoding depends on CPU.}\\
1.13 takayama 737: & & \mbox{\quad\quad Need the byte order negotiation.} \\
1.3 noro 738: \mbox{Array of 128bit machine double} &:&
739: \mbox{({\tt CMO\_ARRAY\_OF\_128BIT\_MACHINE\_DOUBLE}, {\sl int32} m, } \\
1.12 takayama 740: & & \quad \mbox{ {\sl byte} s1[1] , \ldots , {\sl byte} s16[1], \ldots , {\sl byte} s16[m]})\\
1.3 noro 741: & & \mbox{ --- s*[1], $\ldots$ s*[m] are 128bit long double's. } \\
1.12 takayama 742: & & \mbox{ --- Encoding depends on CPU.}\\
1.13 takayama 743: & & \mbox{\quad\quad Need the byte order negotiation.} \\
1.3 noro 744: \end{eqnarray*}
745: */
1.1 noro 746:
747: \bigbreak
1.12 takayama 748:
1.1 noro 749: \begin{verbatim}
750: #define CMO_BIGFLOAT 50
751: #define CMO_IEEE_DOUBLE_FLOAT 51
752: \end{verbatim}
753:
1.3 noro 754: /*&jp
755: IEEE 準拠の float については, IEEE 754 double precision floating-point
756: format (64 bit) の定義を見よ.
1.13 takayama 757:
758: 256.100006 の Intel Pentium の double64 での内部表現は
759: {\tt cd 0c 80 43 } \\
760: 256.100006 の PowerPC (Mac) の double64 での内部表現は
761: {\tt 43 80 0c cd }.
762: この例でみるように byte の順序が逆である.
763: エンジンスタートの時の byte order negotiation で byte の順序を指定する.
764:
765:
1.3 noro 766: */
767: /*&eg
1.5 noro 768: See IEEE 754 double precision floating-point (64 bit) for the details of
1.12 takayama 769: float compliant to the IEEE standard.
1.13 takayama 770:
771: The internal expression of 256.100006 in the Intel Pentium is
772: {\tt cd 0c 80 43 } \\
773: The internal expression of 256.100006 in the PowerPC (Mac) is
774: {\tt 43 80 0c cd }.
775: As you have seen in this example,
776: the orders of the bytes are opposite each other.
777: The byte order is specified by the byte order negotiation protocol
778: when the engine starts.
779:
1.3 noro 780: */
1.1 noro 781:
782: \noindent
1.4 noro 783: Group CMObject/Bigfloat requires CMObject/Primitive, CMObject/Basic.\\
1.1 noro 784: Bigfloat
785: $\in$ CMObject/Bigfloat \\
786:
787: \begin{eqnarray*}
788: \mbox{Bigfloat} &:&
789: \mbox{({\tt CMO\_BIGFLOAT}, } \\
790: & & \quad \mbox{ {\sl ZZ} a , {\sl ZZ} e})\\
1.3 noro 791: & & \mbox{ --- $a \times 2^e$. } \\
1.1 noro 792: \end{eqnarray*}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to cmo-basic1.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / OpenXM-specs