1 #ifndef CoCoA_SmallFpImpl_H 2 #define CoCoA_SmallFpImpl_H 3 4 // Copyright (c) 2005,2009,2011-2015,2018 John Abbott 5 6 // This file is part of the source of CoCoALib, the CoCoA Library. 7 8 // CoCoALib is free software: you can redistribute it and/or modify 9 // it under the terms of the GNU General Public License as published by 10 // the Free Software Foundation, either version 3 of the License, or 11 // (at your option) any later version. 12 13 // CoCoALib is distributed in the hope that it will be useful, 14 // but WITHOUT ANY WARRANTY; without even the implied warranty of 15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 // GNU General Public License for more details. 17 18 // You should have received a copy of the GNU General Public License 19 // along with CoCoALib. If not, see <http://www.gnu.org/licenses/>. 20 21 22 // Header file for the class SmallFpImpl 23 24 25 #include "CoCoA/assert.H" 26 #include "CoCoA/GlobalManager.H" 27 28 29 namespace CoCoA 30 { 31 32 class MachineInt; // fwd decl -- defined in MachineInt.H 33 class BigInt; // fwd decl -- defined in BigInt.H 34 class BigRat; // fwd decl -- defined in BigRat.H 35 class SmallPrime; // fwd decl -- defined in NumTheory-prime.H 36 37 enum SmallFpEnum {SmallFp}; 38 39 class SmallFpImpl 40 { 41 private: 42 public: // BUG!!! ***REMOVE THIS LINE*** when changing to C++11 or later!!! 43 typedef unsigned long repr_t; // ***MUST*** be an unsigned integral type 44 public: 45 class value; 46 class NonRedValue // an unreduced/unnormalized value (as produced by unnorm add/mul). 47 { 48 public: NonRedValue()49 NonRedValue(): myVal(0) {} NonRedValue(value x)50 NonRedValue(value x): myVal(x.myVal) {} 51 // default copy ctor, assignment, dtor all OK 52 friend class SmallFpImpl; // for myNormalize and myHalfNormalize (see below) 53 friend NonRedValue operator+(NonRedValue, NonRedValue); 54 friend NonRedValue operator*(NonRedValue, NonRedValue); 55 friend NonRedValue& operator+=(NonRedValue&, NonRedValue); 56 friend NonRedValue& operator*=(NonRedValue&, NonRedValue); 57 friend std::ostream& operator<<(std::ostream& out, NonRedValue x); 58 // friend repr_t GetRepr(NonRedValue x); 59 private: NonRedValue(repr_t x)60 /*implicit*/ NonRedValue(repr_t x): myVal(x) {} 61 private: // data member -- must be same as data member of value!! 62 repr_t myVal; 63 }; 64 65 class value // a reduced/normalized value 66 { 67 public: value()68 value(): myVal(0) {} 69 // default copy ctor, assignment, dtor all OK 70 friend class SmallFpImpl; 71 friend class NonRedValue; 72 friend value zero(SmallFpEnum); 73 friend value one(SmallFpEnum); 74 friend bool IsZero(value x); 75 friend bool IsOne(value x); 76 friend bool operator==(value x, value y); 77 friend std::ostream& operator<<(std::ostream& out, value x); 78 private: value(repr_t n)79 /*implicit*/ value(repr_t n): myVal(n) {} 80 private: // data member -- must be same as data member of NonRedValue!! 81 repr_t myVal; 82 }; 83 84 public: 85 explicit SmallFpImpl(const MachineInt& n, GlobalSettings::ResidueSetting ResidueChoice = DefaultResidueSetting()); 86 explicit SmallFpImpl(SmallPrime p, GlobalSettings::ResidueSetting ResidueChoice = DefaultResidueSetting()); 87 static bool IsGoodCtorArg(const MachineInt& n); 88 static bool IsGoodCtorArg(SmallPrime p); 89 static long ourMaxModulus(); 90 private: 91 SmallFpImpl(const SmallFpImpl&); // NEVER DEFINED -- copy ctor disabled 92 SmallFpImpl& operator=(const SmallFpImpl&); // NEVER DEFINED -- assignment disabled 93 94 public: 95 static const int ourDatumSize = sizeof(value); 96 97 long myModulus() const; myMaxIters()98 long myMaxIters() const { return myIterLimit; } 99 value myReduce(const MachineInt& n) const; ///< n % myModulus 100 value myReduce(const BigInt& N) const; ///< N % myModulus 101 value myReduce(const BigRat& q) const; ///< q % myModulus (error if den(q)%myModulus == 0) 102 103 long myExportNonNeg(value x) const; ///< exports x into a long (least non neg residue) 104 long myExportSymm(value x) const; ///< exports x into a long (symm residue) 105 long myExport(value x) const; ///< exports x into a long (according to setting myResiduesAreSymm) 106 107 value myNegate(value x) const; 108 value myRecip(value x) const; 109 value myAdd(value x, value y) const; 110 value mySub(value x, value y) const; 111 value myMul(value x, value y) const; 112 value myDiv(value x, value y) const; 113 value myPower(value x, long n) const; 114 value myAddMul(value x, value y, value z) const; /// x+y*z 115 bool myIsZeroAddMul(value& lhs, value y, value z) const;///< lhs += y*z, result says whether lhs == 0. 116 value myNormalize(NonRedValue n) const; 117 NonRedValue myHalfNormalize(NonRedValue n) const; 118 119 private: // Data members 120 const repr_t myModulusValue; 121 const repr_t myHalfWayPoint; 122 const long myIterLimit; 123 const bool myResiduesAreSymm; // Used only in myExport 124 125 friend std::ostream& operator<<(std::ostream& out, const SmallFpImpl& arith); // for access to myResiduesAreSymm 126 127 private: // impl details 128 static repr_t ourCheckCtorArg(const MachineInt& n); 129 static repr_t ourCheckCtorArg(SmallPrime p); 130 static repr_t ourCalcHalfwayPoint(repr_t p); 131 static long ourCalcIterLimit(repr_t p); 132 }; // end of class SmallFpImpl 133 134 135 std::ostream& operator<<(std::ostream& out, const SmallFpImpl& arith); 136 bool operator==(const SmallFpImpl& arith1, const SmallFpImpl& arith2); 137 bool operator!=(const SmallFpImpl& arith1, const SmallFpImpl& arith2); 138 139 std::ostream& operator<<(std::ostream& out, SmallFpImpl::NonRedValue x); 140 std::ostream& operator<<(std::ostream& out, SmallFpImpl::value x); 141 zero(SmallFpEnum)142 inline SmallFpImpl::value zero(SmallFpEnum) { return 0; } one(SmallFpEnum)143 inline SmallFpImpl::value one(SmallFpEnum) { return 1; } 144 145 //------------------------------------------------------------ 146 // SmallFpImpl inline functions 147 //------------------------------------------------------------ 148 149 inline SmallFpImpl::NonRedValue operator+(SmallFpImpl::NonRedValue x, SmallFpImpl::NonRedValue y) 150 { 151 // CoCoA_ASSERT(x.myVal <= std::numeric_limits<decltype(x.myVal)>::max()-y.myVal); 152 CoCoA_ASSERT(x.myVal <= std::numeric_limits<SmallFpImpl::repr_t>::max()-y.myVal); // BUG!!! replace by line above when we switch to C++11 153 return x.myVal + y.myVal; // NOTE: implicit conversion using private ctor 154 } 155 156 inline SmallFpImpl::NonRedValue operator*(SmallFpImpl::NonRedValue x, SmallFpImpl::NonRedValue y) 157 { 158 // CoCoA_ASSERT(y.myVal == 0 || x.myVal <= std::numeric_limits<decltype(x.myVal)>::max()/y.myVal); 159 CoCoA_ASSERT(y.myVal == 0 || x.myVal <= std::numeric_limits<SmallFpImpl::repr_t>::max()/y.myVal); // BUG!!! replace by line above when we switch to C++11 160 return x.myVal * y.myVal; // NOTE: implicit conversion using private ctor 161 } 162 163 inline SmallFpImpl::NonRedValue& operator+=(SmallFpImpl::NonRedValue& lhs, SmallFpImpl::NonRedValue x) 164 { 165 // CoCoA_ASSERT(x.myVal <= std::numeric_limits<decltype(x.myVal)>::max()-y.my 166 CoCoA_ASSERT(lhs.myVal <= std::numeric_limits<SmallFpImpl::repr_t>::max()-x.myVal); // BUG!!! replace by line above when we switch to C++11 167 lhs.myVal += x.myVal; 168 return lhs; 169 } 170 171 inline SmallFpImpl::NonRedValue& operator*=(SmallFpImpl::NonRedValue& lhs, SmallFpImpl::NonRedValue x) 172 { 173 // CoCoA_ASSERT(y.myVal == 0 || x.myVal <= std::numeric_limits<decltype(x.myVal)>::max()/y.myVal); 174 CoCoA_ASSERT(x.myVal == 0 || lhs.myVal <= std::numeric_limits<SmallFpImpl::repr_t>::max()/x.myVal); // BUG!!! replace by line above when we switch to C++11 175 lhs.myVal *= x.myVal; 176 return lhs; 177 } 178 179 180 // inline SmallFpImpl::repr_t GetRepr(SmallFpImpl::NonRedValue x) 181 // { 182 // return x.myVal; 183 // } 184 185 myAddMul(SmallFpImpl::value x,SmallFpImpl::value y,SmallFpImpl::value z)186 inline SmallFpImpl::value SmallFpImpl::myAddMul(SmallFpImpl::value x, SmallFpImpl::value y, SmallFpImpl::value z) const 187 { 188 CoCoA_ASSERT(y.myVal == 0 || z.myVal <= std::numeric_limits<repr_t>::max()/y.myVal); 189 CoCoA_ASSERT(y.myVal*z.myVal <= std::numeric_limits<repr_t>::max()-x.myVal); 190 return myNormalize(x.myVal + y.myVal * z.myVal); 191 } 192 193 IsZero(SmallFpImpl::value x)194 inline bool IsZero(SmallFpImpl::value x) 195 { 196 return x.myVal == 0; 197 } 198 IsOne(SmallFpImpl::value x)199 inline bool IsOne(SmallFpImpl::value x) 200 { 201 return x.myVal == 1; 202 } 203 204 205 inline bool operator==(SmallFpImpl::value x, SmallFpImpl::value y) 206 { 207 return x.myVal == y.myVal; 208 } 209 210 inline bool operator!=(SmallFpImpl::value x, SmallFpImpl::value y) 211 { 212 return !(x == y); 213 } 214 215 216 217 myModulus()218 inline long SmallFpImpl::myModulus() const 219 { 220 return myModulusValue; // implicit cast is safe 221 } 222 223 myExportNonNeg(value x)224 inline long SmallFpImpl::myExportNonNeg(value x) const 225 { 226 return x.myVal; // implicit cast is safe 227 } 228 myExportSymm(value x)229 inline long SmallFpImpl::myExportSymm(value x) const 230 { 231 if (x.myVal <= myModulusValue/2) return x.myVal; // implicit cast is safe 232 return -static_cast<long>(myModulusValue - x.myVal); // cast is safe 233 } 234 myExport(value x)235 inline long SmallFpImpl::myExport(value x) const 236 { 237 if (myResiduesAreSymm) return myExportSymm(x); 238 return myExportNonNeg(x); 239 // if (!myResiduesAreSymm || x.myVal <= myModulusValue/2) return x.myVal; // implicit cast is safe 240 // return -static_cast<long>(myModulusValue - x.myVal); // cast is safe 241 } 242 243 myNormalize(NonRedValue n)244 inline SmallFpImpl::value SmallFpImpl::myNormalize(NonRedValue n) const 245 { 246 return n.myVal%myModulusValue; 247 } 248 myHalfNormalize(NonRedValue n)249 inline SmallFpImpl::NonRedValue SmallFpImpl::myHalfNormalize(NonRedValue n) const 250 { 251 if (n.myVal >= myHalfWayPoint) 252 n.myVal -= myHalfWayPoint; 253 return n; 254 } 255 256 myNegate(value x)257 inline SmallFpImpl::value SmallFpImpl::myNegate(value x) const 258 { 259 CoCoA_ASSERT(x == myNormalize(x)); 260 if (IsZero(x)) return x; 261 return myModulusValue - x.myVal; 262 } 263 264 myAdd(value x,value y)265 inline SmallFpImpl::value SmallFpImpl::myAdd(value x, value y) const 266 { 267 CoCoA_ASSERT(x == myNormalize(x)); 268 CoCoA_ASSERT(y == myNormalize(y)); 269 const repr_t ans = x.myVal + y.myVal; 270 if (ans < myModulusValue) return ans; 271 return ans - myModulusValue; 272 } 273 274 mySub(value x,value y)275 inline SmallFpImpl::value SmallFpImpl::mySub(value x, value y) const 276 { 277 CoCoA_ASSERT(x == myNormalize(x)); 278 CoCoA_ASSERT(y == myNormalize(y)); 279 if (x.myVal >= y.myVal) return x.myVal - y.myVal; 280 return x.myVal + (myModulusValue-y.myVal); // avoid trying to create a negative value 281 } 282 283 myMul(value x,value y)284 inline SmallFpImpl::value SmallFpImpl::myMul(value x, value y) const 285 { 286 CoCoA_ASSERT(x == myNormalize(x)); 287 CoCoA_ASSERT(y == myNormalize(y)); 288 return (x.myVal*y.myVal)%myModulusValue; // overflow cannot occur! 289 } 290 291 myIsZeroAddMul(value & lhs,value y,value z)292 inline bool SmallFpImpl::myIsZeroAddMul(value& lhs, value y, value z) const 293 { 294 CoCoA_ASSERT(y == myNormalize(y)); 295 CoCoA_ASSERT(z == myNormalize(z)); 296 CoCoA_ASSERT(lhs == myNormalize(lhs)); 297 lhs = (lhs.myVal + y.myVal * z.myVal)%myModulusValue; // overflow cannot occur! 298 return IsZero(lhs); 299 } 300 301 302 inline bool operator==(const SmallFpImpl& arith1, const SmallFpImpl& arith2) 303 { 304 return (arith1.myModulus() == arith2.myModulus()); 305 } 306 307 inline bool operator!=(const SmallFpImpl& arith1, const SmallFpImpl& arith2) 308 { 309 return !(arith1 == arith2); 310 } 311 312 } // end of namespace CoCoA 313 314 315 // RCS header/log in the next few lines 316 // $Header: /Volumes/Home_1/cocoa/cvs-repository/CoCoALib-0.99/include/CoCoA/SmallFpImpl.H,v 1.33 2020/01/26 14:17:55 abbott Exp $ 317 // $Log: SmallFpImpl.H,v $ 318 // Revision 1.33 2020/01/26 14:17:55 abbott 319 // Summary: Changed include of MachineInt into fwd decl 320 // 321 // Revision 1.32 2018/06/25 12:28:20 abbott 322 // Summary: Ctors now accept SmallPrime args (and skip primality tests) 323 // 324 // Revision 1.31 2018/02/27 10:52:42 abbott 325 // Summary: Updated to offer special ctor for SmallPrime arg (no need to check primality) 326 // 327 // Revision 1.30 2018/02/15 17:26:11 abbott 328 // Summary: Added EratosthenesRange, and PrimeSeq 329 // 330 // Revision 1.29 2018/01/18 14:50:05 abbott 331 // Summary: Corrected a check in operator* or NonRedValue 332 // 333 // Revision 1.28 2018/01/17 10:27:25 abbott 334 // Summary: Corrected private implicit ctor for value; added useful comments 335 // 336 // Revision 1.27 2018/01/11 17:16:19 abbott 337 // Summary: Removed embarassing bug in private ctor for NonRedValue (arg type was uint) 338 // 339 // Revision 1.26 2016/03/25 20:22:48 abbott 340 // Summary: Minor reordering of source code 341 // 342 // Revision 1.25 2015/12/11 13:08:11 abbott 343 // Summary: Added myExportNonNeg and myExportSymm 344 // 345 // Revision 1.24 2015/12/02 15:30:49 abbott 346 // Summary: Added op!= 347 // 348 // Revision 1.23 2015/11/04 10:09:47 abbott 349 // Summary: MAJOR REVISION to handle cleanly non-reduced values 350 // 351 // Revision 1.22 2015/10/09 18:28:44 abbott 352 // Summary: Corrected redmine reference 353 // 354 // Revision 1.21 2015/10/09 18:18:27 abbott 355 // Summary: Renamed "abs" to "uabs" for MachineInt; new fn "negate"; see redmine 783 356 // 357 // Revision 1.20 2014/11/27 11:28:51 abbott 358 // Summary: Corrected signature of mul 359 // Author: JAA 360 // 361 // Revision 1.19 2014/11/18 15:46:48 abbott 362 // Summary: intermediate check in (new and old impls together) 363 // Author: JAA 364 // 365 // Revision 1.18 2013/05/27 14:05:44 abbott 366 // Removed typedefs SmallFpElem_t and SmallFpLogElem_t from config.H; 367 // they are now nest typedefs SmallFpImpl::value_t and SmallFpLogImpl::value_t. 368 // 369 // Revision 1.17 2013/03/25 17:04:19 abbott 370 // Major clean-up of interface to SmallFpImpl/SmallFpLogImpl/SmallFpDoubleImpl 371 // (underlying impl remains much the same). Removed lots of cruft. 372 // Consequential changes to RingFp* classes; small change to SparsePolyRing. 373 // 374 // Revision 1.16 2013/02/21 13:00:37 abbott 375 // Added new fn operator!= 376 // 377 // Revision 1.15 2012/11/23 17:26:45 abbott 378 // Added mem fn myResidueUPB. 379 // 380 // Revision 1.14 2012/10/04 08:57:28 abbott 381 // Added keyword const to a local variable. 382 // 383 // Revision 1.13 2012/09/07 15:21:13 abbott 384 // First stage of revision of SmallFpImpl interface (and SmallFpLog, SmallFpDouble). 385 // 386 // Revision 1.12 2012/01/30 11:01:11 abbott 387 // Added naive printing fn (just to help during debugging). 388 // 389 // Revision 1.11 2011/11/09 13:50:01 bigatti 390 // -- renamed MachineInteger --> MachineInt 391 // 392 // Revision 1.10 2011/08/24 10:21:09 bigatti 393 // -- renamed QQ --> BigRat 394 // 395 // Revision 1.9 2011/08/14 15:52:17 abbott 396 // Changed ZZ into BigInt (phase 1: just the library sources). 397 // 398 // Revision 1.8 2011/05/20 19:26:05 abbott 399 // Updated SmallFp*Impl: removed all output-related fns (must use myExport instead). 400 // 401 // Revision 1.7 2011/05/19 14:38:27 abbott 402 // Updated small prime finite field impls to allow user to specify 403 // separately for each whether to use symmetric or non-negative 404 // residues for export operations (myExport and printing). 405 // 406 // Revision 1.6 2011/03/22 20:06:13 abbott 407 // Added static mem fn IsGoodCtorArg (called by RingFp pseudo-ctors). 408 // Commented out ctors which take ZZ arg -- seems useless. 409 // 410 // Revision 1.5 2011/03/14 10:28:15 abbott 411 // Changed unsigned long into long (and unsigned short into short). 412 // 413 // Revision 1.4 2009/05/14 09:39:29 abbott 414 // Added possibility to specify "symmetric" or "non-negative" residues 415 // in quotients of ZZ. Affects printing of elements in quotients of ZZ 416 // (also changed printing of elements in general quotient rings). 417 // Consequent changes in several tests. 418 // 419 // Revision 1.3 2008/12/17 12:11:52 abbott 420 // Changed type from long to MachineInt in operations which use a machine integer 421 // in place of a RingElem. The change is "superficial" but affects many files. 422 // 423 // Revision 1.2 2007/10/30 17:14:11 abbott 424 // Changed licence from GPL-2 only to GPL-3 or later. 425 // New version for such an important change. 426 // 427 // Revision 1.1.1.1 2007/03/09 15:16:11 abbott 428 // Imported files 429 // 430 // Revision 1.7 2007/03/08 18:42:05 cocoa 431 // Cleaned up whitespace. 432 // 433 // Revision 1.6 2007/01/11 14:07:42 cocoa 434 // -- changed names to arguments called "rsh" 435 // 436 // Revision 1.5 2006/12/06 17:30:02 cocoa 437 // -- rearranged #include 438 // 439 // Revision 1.4 2006/11/24 17:22:05 cocoa 440 // -- removed OpenMathFwd.H 441 // 442 // Revision 1.3 2006/11/02 13:25:44 cocoa 443 // Simplification of header files: the OpenMath classes have been renamed. 444 // Many minor consequential changes. 445 // 446 // Revision 1.2 2006/10/06 14:04:15 cocoa 447 // Corrected position of #ifndef in header files. 448 // Separated CoCoA_ASSERT into assert.H from config.H; 449 // many minor consequential changes (have to #include assert.H). 450 // A little tidying of #include directives (esp. in Max's code). 451 // 452 // Revision 1.1.1.1 2006/05/30 11:39:37 cocoa 453 // Imported files 454 // 455 // Revision 1.4 2006/05/12 16:10:58 cocoa 456 // Added OpenMathFwd.H, and tidied OpenMath.H. 457 // Many consequential but trivial changes. 458 // 459 // Revision 1.3 2006/03/27 12:21:26 cocoa 460 // Minor silly changes to reduce number of complaints from some compiler or other. 461 // 462 // Revision 1.2 2006/03/12 21:28:34 cocoa 463 // Major check in after many changes 464 // 465 // Revision 1.1.1.1 2005/10/17 10:46:54 cocoa 466 // Imported files 467 // 468 // Revision 1.5 2005/10/14 15:25:07 cocoa 469 // Major tidying and cleaning to small prime finite fields. 470 // Several consequential changes. Improved their documentation. 471 // 472 // Added Makefile and script to include/CoCoA/ directory to 473 // keep library.H up to date. 474 // 475 // Revision 1.4 2005/10/12 15:52:09 cocoa 476 // Completed test-RingFp1 and corrected/cleaned the SmallFp* 477 // and RingFp* files. 478 // 479 // Some minor tidying elsewhere. 480 // 481 // Revision 1.3 2005/10/11 16:37:30 cocoa 482 // Added new small prime finite field class (see RingFpDouble). 483 // 484 // Cleaned makefiles and configuration script. 485 // 486 // Tidied PPMonoid code (to eliminate compiler warnings). 487 // 488 // Fixed bug in RingFloat::myIsInteger. 489 // 490 // Revision 1.2 2005/09/22 18:04:17 cocoa 491 // It compiles; the tests run OK. The examples compile. 492 // No documentation -- the mindless eurocrats have rendered 493 // me mindless too. 494 // 495 // Revision 1.1.1.1 2005/05/03 15:47:31 cocoa 496 // Imported files 497 // 498 // Revision 1.4 2005/04/19 14:06:04 cocoa 499 // Added GPL and GFDL licence stuff. 500 // 501 // Revision 1.3 2005/02/28 15:58:56 cocoa 502 // Resynch after some minor changes. 503 // 504 // Revision 1.2 2005/02/11 16:45:24 cocoa 505 // Removed the useless and misleading functions myInit and myKill 506 // from the SmallFp*Impl classes; various consequential changes. 507 // 508 // Revision 1.1.1.1 2005/01/27 15:12:13 cocoa 509 // Imported files 510 // 511 // Revision 1.7 2004/11/12 15:49:29 cocoa 512 // Tidying prior to 0.90 release. 513 // (a) documentation improved (or marked as poor) 514 // (b) sundry minor improvements to the code 515 // 516 // Revision 1.6 2004/11/11 13:05:49 cocoa 517 // -- added \include *.txt for doxygen 518 // 519 // Revision 1.5 2004/11/04 18:47:42 cocoa 520 // (1) Ring member functions which previously expected mpz_t args 521 // now expect ZZ args. Numerous minor consequential changes. 522 // (2) Renamed function which gives access to the mpz_t value inside 523 // a ZZ object: previously was raw(...), now is mpzref(...). 524 // Plenty of calls had to be altered. 525 // 526 // Revision 1.4 2004/07/20 15:04:06 cocoa 527 // The next step in the new "ring element" conversion process: 528 // handling the case of creating a "const RefRingElem" object 529 // (since C++ refuses to do this properly itself). 530 // 531 // Revision 1.3 2004/07/16 15:45:12 cocoa 532 // First stage of new RingElem implementation completed. 533 // 534 // Revision 1.2 2004/07/14 16:40:42 cocoa 535 // Separated RingFpLog from its implementation which now resides in 536 // a new class: SmallFpLogImpl. This is analogous to the change made 537 // to RingFp yesterday. 538 // 539 // Some tidying and other sundry minor changes. 540 // 541 // Revision 1.1 2004/07/13 16:32:26 cocoa 542 // First stage of major revamp of ring elements. 543 // Implementation of RingFp has been split into "ring interface" 544 // and "algorithms plus data structures". 545 // 546 // 547 548 549 #endif 550