Implements some fast basic operations for elemens of a ring F_q[epsilon] or field F_q with small characteristic;
For all operations the user must be sure that the operators are regular represantants of ring elements, in doubt by calling the Convert() function. Currently all represantant values must lie between 0 and (characteristic-1). Allowed 'eps' precisions are 0 (is a field) and 1 (is a ring)
Parametrized with element Type (TNum) and characteristic of the field the ring is based on during compile time.
More...
#include <fast_Ring.h>
Classes | |
struct | sqrtInf |
Public Types | |
typedef struct fast_Ring::sqrtInf | sqrtInf_t |
typedef TNum | ElementType |
typedef fast_Ring< TNum, kdefs > | FieldType |
typedef FieldType::ElementType | ScalarType |
Public Member Functions | |
bool | wellDefined () |
const FieldType * | getField () const |
const FieldType & | getFieldRef () const |
Constructors / Destructors | |
fast_Ring (unsigned short _characteristic, unsigned short epsPrec) | |
~fast_Ring () | |
properties | |
unsigned short | getCharacteristic () const |
const unsigned short & | getCharacteristicRef () const |
unsigned short | getEpsPrecision () const |
void | setEpsPrecision (int epsPrecision) const |
safety | |
bool | isValid (TNum a) const |
add | |
TNum | add (const TNum a, const TNum b) const |
TNum | addRef (const TNum &a, const TNum &b) const |
add in place | |
void | addInPlace (TNum &a, const TNum b) const |
void | addInPlaceRef (TNum &a, const TNum &b) const |
additive inverse | |
TNum | addInv (const TNum a) const |
TNum | addInvRef (const TNum &a) const |
void | addInvInPlace (TNum &a) const |
accMult | |
void | accMult (TNum &a, const TNum b, const TNum c) const |
void | accMultRef (TNum &a, const TNum &b, const TNum &c) const |
void | accMult (TNum *a, const TNum b, const TNum c) const |
void | accMultAddr (TNum *a, const TNum *b, const TNum *c) const |
accMult assumes, that b is not zero, and | |
void | accMultSpec (TNum *const a, const TNum b, const TNum *const c) const |
multiplication | |
TNum | multiply (const TNum a, const TNum b) const |
TNum | multiplyRef (const TNum &a, const TNum &b) const |
multipliziert zwei Zahlen | |
multiply in place | |
void | multiplyInPlace (TNum &a, const TNum b) const |
void | multiplyInPlaceRef (TNum &a, const TNum &b) const |
scalar multiplication | |
TNum | scalarMultiply (const FieldType::ElementType a, const TNum b) const |
TNum | scalarMultiplyRef (const FieldType::ElementType &a, const TNum &b) const |
multipliziert zwei Zahlen | |
scalar multiply in place | |
void | scalarMultiplyInPlace (const FieldType::ElementType a, TNum &b) const |
void | scalarMultiplyInPlaceRef (const FieldType::ElementType &a, TNum &b) const |
multiplication by Exponents | |
TNum const | multByExp (const TNum a, const TNum b) const |
TNum const | multByExpRef (const TNum &a, const TNum &b) const |
void | multByExpInPlace (TNum &a, const TNum b) const |
void | multByExpInPlaceRef (TNum &a, const TNum &b) const |
multiplicative inverse | |
TNum | multInv (const TNum a) const |
TNum | multInvRef (const TNum &a) const |
void | multInvInPlace (TNum &a) const |
power | |
TNum | pow (TNum const a, unsigned int exp) const |
void | powInPlace (TNum &a, unsigned int exp) const |
sqrd | |
sqrtInf | sqrt (const TNum a) const |
sqrtInf | sqrtRef (const TNum &a) const |
Conversion | |
FieldType::ElementType | lookupModuloTable (int convertee) const |
int | getLookupModuloTableSize () const |
template<class TConvNum > | |
TNum | Convert (const TConvNum a) const |
TNum | Convert (const double a) const |
Convert eventuell umbenennen ConvertScalarToRingElement | |
TNum | Convert (const int a) const |
Convert eventuell umbenennen ConvertScalarToRingElement | |
template<class TConvNum > | |
void | ConvertInPlace (TConvNum &a) const |
int | ConvertScalar (const int a) const |
einfuehren ConvertScalarToFieldElement | |
int | ConvertScalarSpec (const int a) const |
convert a integer to Ring element. Assumption: a >=0 | |
int | FastConvertScalar (const int a) const |
convert a integer to Ring Elemen. Assumption: a >=-getCharacteristic() / | |
Table index computation | |
size_t | getMaxSingleIndex () const |
size_t | getMaxPairIndex () const |
size_t | getSingleIndex (const TNum z1) const |
size_t | getSingleIndexByRef (const TNum &z1) const |
size_t | getPairIndexByRef (const TNum &z1, const TNum &z2) const |
size_t | getPairIndex (const TNum z1, const TNum z2) const |
Protected Member Functions | |
void | init () |
TNum * | createAdditionTable () |
only for the case, that table pointers are static | |
TNum * | createMultiplicationTable () |
creates multiplication table | |
TNum * | createSubtractionTable () |
TNum * | createAdditiveInverseTable () |
TNum * | createMultiplicativeInverseTable () |
TNum | getGenerator () |
Returns a generator of the Ring0} if exists, otherwise TNum::Zero. | |
TNum * | initElementsToExponentsTab (TNum erzeuger) |
TNum * | initExponentsToElementTab (TNum erzeuger) |
TNum * | createFastAdditionTable () |
only for epsilon==0 | |
FieldType::ElementType * | createModuloTable () |
sqrtInf_t * | createSqrtTable () |
Private Attributes | |
const unsigned short | characteristic |
long | moduloTableSize_m |
const unsigned short | epsilon |
const TNum | generator |
const TNum * | elementsToExponentsTab |
const TNum * | exponentsToElementTab |
const TNum * | additiveInverseTable |
const TNum * | multiplicationTable |
const TNum * | additionTable |
const TNum * | multiplicativeInverseTable |
const TNum * | fastAdditionTable |
const ScalarType * | moduloTable |
const sqrtInf_t * | sqrtTable |
Main idea: table lookup instead of computation. For big characteristics this method costs performance, because the operation lookup tables does not fit in L1 or L2 cache But for small characteristics it works very well.
To avoid copying data, functions with reference parameters were implemented, because it is impossible to enforce inlining. But that costs implementation overhead and is dangerous, because is is possible to pass a reference to a temporary variable. and woult result in an error.
Die Schnelligkeit der Berechnungen beruht auf Verwendung von Operationstabellen und von der Annahme, dass alle Funktionsaufrufe mit gültigen Parametern ausgeführt werden. Die Operationstabellen sind so ausgelegt, dass mit Hilfe von Bit Shift Operationen das Ergebnis einer Rechenoperation abgelesen werden kann: statt
ArrayIndex(a,b)=a*charakteristik+b
ArrayIndex(a,b)=a*Zweierpotenz+b benutzt wird.; Zweierpotenz>=charakteristik, Somit kann die Indexfunktion mit Bit Schifts und bitweisem 'OR' berechnet werden Der Nachteil ist, dass mehr Speicherplatz, als benötigt belegt wird.
Die Berechnungen werden wieder langsamer, wenn die Tabellen nicht in den Cache passen. Bei Charakteristik 29 und dem Zahlentype 'number_eps1' beträgt der Speicherplatzbedarf 29^4*2 Bytes * 2 Tabellen (Multiplikation, Addition) = 4 MByte und bei Charakteristik 23 1119364 = 1 MByte
Definition at line 92 of file fast_Ring.h.
typedef TNum fast_Ring< TNum, kdefs >::ElementType |
Definition at line 108 of file fast_Ring.h.
typedef fast_Ring< TNum,kdefs > fast_Ring< TNum, kdefs >::FieldType |
Definition at line 110 of file fast_Ring.h.
typedef FieldType::ElementType fast_Ring< TNum, kdefs >::ScalarType |
Definition at line 112 of file fast_Ring.h.
typedef struct fast_Ring::sqrtInf fast_Ring< TNum, kdefs >::sqrtInf_t |
fast_Ring< TNum, kdefs >::fast_Ring | ( | unsigned short | _char, | |
unsigned short | _epsPrec | |||
) | [inline] |
Definition at line 13 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::characteristic, fast_Ring< TNum, kdefs >::epsilon, fast_Ring< TNum, kdefs >::init(), and fast_Ring< TNum, kdefs >::wellDefined().
Definition at line 95 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::additiveInverseTable, fast_Ring< TNum, kdefs >::elementsToExponentsTab, fast_Ring< TNum, kdefs >::exponentsToElementTab, fast_Ring< TNum, kdefs >::fastAdditionTable, fast_Ring< TNum, kdefs >::moduloTable, fast_Ring< TNum, kdefs >::multiplicationTable, fast_Ring< TNum, kdefs >::multiplicativeInverseTable, and fast_Ring< TNum, kdefs >::sqrtTable.
void fast_Ring< TNum, kdefs >::accMult | ( | TNum * | a, | |
const TNum | b, | |||
const TNum | c | |||
) | const [inline] |
Definition at line 656 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndex(), and fast_Ring< TNum, kdefs >::multiplicationTable.
void fast_Ring< TNum, kdefs >::accMult | ( | TNum & | a, | |
const TNum | b, | |||
const TNum | c | |||
) | const [inline] |
Definition at line 641 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndex(), and fast_Ring< TNum, kdefs >::multiplicationTable.
void fast_Ring< TNum, kdefs >::accMultAddr | ( | TNum * | a, | |
const TNum * | b, | |||
const TNum * | c | |||
) | const [inline] |
Definition at line 763 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndex(), and fast_Ring< TNum, kdefs >::multiplicationTable.
void fast_Ring< TNum, kdefs >::accMultRef | ( | TNum & | a, | |
const TNum & | b, | |||
const TNum & | c | |||
) | const [inline] |
Definition at line 673 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndex(), fast_Ring< TNum, kdefs >::getPairIndexByRef(), and fast_Ring< TNum, kdefs >::multiplicationTable.
void fast_Ring< TNum, kdefs >::accMultSpec | ( | TNum *const | a, | |
const TNum | b, | |||
const TNum *const | c | |||
) | const [inline] |
Optimierung : Eigenen Überlegungen nach sollte die Multiplikation an dieser Stelle per Tabelle und die Addition auf der CPU erledigt werden, weil ein Multiplikator fest ist und nur der andere variiert ( characteristic*characteristic mögliche Werte) Dagegen variieren bei der Addition beide Zahlen, was zu erheblichen Cache misses führen müsste. Allerdings ist die Laufzeit auf einem Intel-Rechner katastrophal, wenn man die Addition auf der CPU durchführt. Es gab mal eine Konfiguration, wo die Addition auf der CPU schneller war, jetzt ist die Laufzeit in etwa gleich, oder schlechter mit der Addition auf der CPU
Definition at line 698 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndex(), and fast_Ring< TNum, kdefs >::multiplicationTable.
TNum fast_Ring< TNum, kdefs >::add | ( | const TNum | a, | |
const TNum | b | |||
) | const [inline] |
Definition at line 290 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::Convert(), and fast_Ring< TNum, kdefs >::getPairIndex().
void fast_Ring< TNum, kdefs >::addInPlace | ( | TNum & | a, | |
const TNum | b | |||
) | const [inline] |
Definition at line 319 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::Convert(), and fast_Ring< TNum, kdefs >::getPairIndex().
void fast_Ring< TNum, kdefs >::addInPlaceRef | ( | TNum & | a, | |
const TNum & | b | |||
) | const [inline] |
Definition at line 334 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::Convert(), and fast_Ring< TNum, kdefs >::getPairIndexByRef().
TNum fast_Ring< TNum, kdefs >::addInv | ( | const TNum | a | ) | const [inline] |
Definition at line 352 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additiveInverseTable, fast_Ring< TNum, kdefs >::Convert(), and fast_Ring< TNum, kdefs >::getSingleIndex().
void fast_Ring< TNum, kdefs >::addInvInPlace | ( | TNum & | a | ) | const [inline] |
Definition at line 375 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additiveInverseTable, fast_Ring< TNum, kdefs >::Convert(), and fast_Ring< TNum, kdefs >::getSingleIndexByRef().
TNum fast_Ring< TNum, kdefs >::addInvRef | ( | const TNum & | a | ) | const [inline] |
Definition at line 364 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additiveInverseTable, fast_Ring< TNum, kdefs >::Convert(), and fast_Ring< TNum, kdefs >::getSingleIndexByRef().
TNum fast_Ring< TNum, kdefs >::addRef | ( | const TNum & | a, | |
const TNum & | b | |||
) | const [inline] |
Definition at line 303 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::Convert(), and fast_Ring< TNum, kdefs >::getPairIndexByRef().
TNum fast_Ring< TNum, kdefs >::Convert | ( | const int | a | ) | const [inline] |
Definition at line 180 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::ConvertScalar(), and fast_Ring< TNum, kdefs >::getEpsPrecision().
TNum fast_Ring< TNum, kdefs >::Convert | ( | const double | a | ) | const [inline] |
Definition at line 166 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::ConvertScalar(), and fast_Ring< TNum, kdefs >::getEpsPrecision().
TNum fast_Ring< TNum, kdefs >::Convert | ( | const TConvNum | src | ) | const [inline] |
src | TConvNum object src must implement getX() and getEps() -Interface . In general this can be replaced by getValue(epsPrecision)-Interface, but is not neccessary in this specialized class |
Definition at line 142 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::ConvertScalar(), and fast_Ring< TNum, kdefs >::getEpsPrecision().
Referenced by fast_Ring< TNum, kdefs >::accMult(), fast_Ring< TNum, kdefs >::accMultAddr(), fast_Ring< TNum, kdefs >::accMultRef(), fast_Ring< TNum, kdefs >::accMultSpec(), fast_Ring< TNum, kdefs >::add(), fast_Ring< TNum, kdefs >::addInPlace(), fast_Ring< TNum, kdefs >::addInPlaceRef(), fast_Ring< TNum, kdefs >::addInv(), fast_Ring< TNum, kdefs >::addInvInPlace(), fast_Ring< TNum, kdefs >::addInvRef(), fast_Ring< TNum, kdefs >::addRef(), fast_Ring< TNum, kdefs >::isValid(), fast_Ring< TNum, kdefs >::multInv(), fast_Ring< TNum, kdefs >::multInvInPlace(), fast_Ring< TNum, kdefs >::multInvRef(), fast_Ring< TNum, kdefs >::multiply(), fast_Ring< TNum, kdefs >::multiplyInPlace(), fast_Ring< TNum, kdefs >::multiplyInPlaceRef(), fast_Ring< TNum, kdefs >::multiplyRef(), fast_Ring< TNum, kdefs >::scalarMultiply(), fast_Ring< TNum, kdefs >::scalarMultiplyInPlace(), fast_Ring< TNum, kdefs >::scalarMultiplyInPlaceRef(), fast_Ring< TNum, kdefs >::scalarMultiplyRef(), fast_Ring< TNum, kdefs >::sqrt(), and fast_Ring< TNum, kdefs >::sqrtRef().
void fast_Ring< TNum, kdefs >::ConvertInPlace | ( | TConvNum & | a | ) | const [inline] |
riscy in some cases? does currently ignore the case where TConvNum.getEpsPrecision > 1. assert( getEpsPrecision()<=1 ); gehoert in den Konstruktor dieser Klasse, da sie offenbar nicht mit EPSPrecision >1 arbeiten kann und muss. An anderen Stellen kann diese Abfrage entfernt werden.
Definition at line 218 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::ConvertScalar(), and fast_Ring< TNum, kdefs >::getEpsPrecision().
int fast_Ring< TNum, kdefs >::ConvertScalar | ( | const int | a | ) | const [inline] |
Definition at line 239 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
Referenced by fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::ConvertInPlace(), and fast_Ring< TNum, kdefs >::lookupModuloTable().
int fast_Ring< TNum, kdefs >::ConvertScalarSpec | ( | const int | a | ) | const [inline] |
Definition at line 261 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
TNum * fast_Ring< TNum, kdefs >::createAdditionTable | ( | ) | [inline, protected] |
create addition table
Initialisiert die Additionstabelle . Es gibt zwei Faelle: epsPrecision==0 und epsPrecision==1 Bei epsPrecision =0 sind die Eintraege eindimensional (x) und fuer epsPrecision==1 zweidimensional (x,eps).
Optimierungsmoeglichkeit: steht wenig cache zur Verfuegung, so kann der Cache-Bedarf um die Haelfte reduziert werden, wenn die Additionstabelle nur Eindimensional angelegt wird und die add-Funktionen bei epsPrecision==1 (x1,eps1)+(x2,eps2) simulieren.
Definition at line 842 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic(), fast_Ring< TNum, kdefs >::getEpsPrecision(), fast_Ring< TNum, kdefs >::getMaxPairIndex(), and fast_Ring< TNum, kdefs >::getPairIndex().
Referenced by fast_Ring< TNum, kdefs >::init().
TNum * fast_Ring< TNum, kdefs >::createAdditiveInverseTable | ( | ) | [inline, protected] |
Definition at line 903 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic(), fast_Ring< TNum, kdefs >::getEpsPrecision(), fast_Ring< TNum, kdefs >::getMaxSingleIndex(), and fast_Ring< TNum, kdefs >::getSingleIndex().
Referenced by fast_Ring< TNum, kdefs >::init().
TNum * fast_Ring< TNum, kdefs >::createFastAdditionTable | ( | ) | [inline, protected] |
Definition at line 879 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic(), and fast_Ring< TNum, kdefs >::getEpsPrecision().
Referenced by fast_Ring< TNum, kdefs >::init().
fast_Ring< TNum, kdefs >::FieldType::ElementType * fast_Ring< TNum, kdefs >::createModuloTable | ( | ) | [inline, protected] |
Definition at line 1110 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::characteristic, and fast_Ring< TNum, kdefs >::moduloTableSize_m.
Referenced by fast_Ring< TNum, kdefs >::init().
TNum * fast_Ring< TNum, kdefs >::createMultiplicationTable | ( | ) | [inline, protected] |
Definition at line 932 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic(), fast_Ring< TNum, kdefs >::getEpsPrecision(), fast_Ring< TNum, kdefs >::getMaxPairIndex(), and fast_Ring< TNum, kdefs >::getPairIndex().
Referenced by fast_Ring< TNum, kdefs >::init().
TNum * fast_Ring< TNum, kdefs >::createMultiplicativeInverseTable | ( | ) | [inline, protected] |
creates multiplicative inverse table
in den Initialisierungsfunktionen die Convert-Funktion nutzen!
initInv überarbeiten!
Definition at line 998 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic(), fast_Ring< TNum, kdefs >::getEpsPrecision(), fast_Ring< TNum, kdefs >::getMaxSingleIndex(), and fast_Ring< TNum, kdefs >::getSingleIndex().
Referenced by fast_Ring< TNum, kdefs >::init().
fast_Ring< TNum, kdefs >::sqrtInf_t * fast_Ring< TNum, kdefs >::createSqrtTable | ( | ) | [inline, protected] |
Definition at line 1160 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic(), fast_Ring< TNum, kdefs >::getMaxSingleIndex(), fast_Ring< TNum, kdefs >::sqrtInf::solutions, fast_Ring< TNum, kdefs >::sqrt(), and fast_Ring< TNum, kdefs >::sqrtInf::sqrt.
Referenced by fast_Ring< TNum, kdefs >::init().
TNum* fast_Ring< TNum, kdefs >::createSubtractionTable | ( | ) | [protected] |
int fast_Ring< TNum, kdefs >::FastConvertScalar | ( | const int | a | ) | const [inline] |
Definition at line 275 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
unsigned short fast_Ring< TNum, kdefs >::getCharacteristic | ( | ) | const [inline] |
Definition at line 172 of file fast_Ring.h.
References fast_Ring< TNum, kdefs >::characteristic.
Referenced by fast_Ring< TNum, kdefs >::ConvertScalar(), fast_Ring< TNum, kdefs >::ConvertScalarSpec(), fast_Ring< TNum, kdefs >::createAdditionTable(), fast_Ring< TNum, kdefs >::createAdditiveInverseTable(), fast_Ring< TNum, kdefs >::createFastAdditionTable(), fast_Ring< TNum, kdefs >::createMultiplicationTable(), fast_Ring< TNum, kdefs >::createMultiplicativeInverseTable(), fast_Ring< TNum, kdefs >::createSqrtTable(), fast_Ring< TNum, kdefs >::FastConvertScalar(), fast_Ring< TNum, kdefs >::getGenerator(), fast_Ring< TNum, kdefs >::getMaxPairIndex(), fast_Ring< TNum, kdefs >::getMaxSingleIndex(), fast_Ring< TNum, kdefs >::getPairIndex(), fast_Ring< TNum, kdefs >::getSingleIndex(), fast_Ring< TNum, kdefs >::initElementsToExponentsTab(), fast_Ring< TNum, kdefs >::initExponentsToElementTab(), fast_Ring< TNum, kdefs >::multByExp(), fast_Ring< TNum, kdefs >::multByExpInPlace(), fast_Ring< TNum, kdefs >::multByExpInPlaceRef(), and fast_Ring< TNum, kdefs >::multByExpRef().
const unsigned short& fast_Ring< TNum, kdefs >::getCharacteristicRef | ( | ) | const [inline] |
Definition at line 173 of file fast_Ring.h.
References fast_Ring< TNum, kdefs >::characteristic.
Referenced by fast_Ring< TNum, kdefs >::getPairIndexByRef(), and fast_Ring< TNum, kdefs >::getSingleIndexByRef().
unsigned short fast_Ring< TNum, kdefs >::getEpsPrecision | ( | ) | const [inline] |
Definition at line 175 of file fast_Ring.h.
References fast_Ring< TNum, kdefs >::epsilon.
Referenced by fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::ConvertInPlace(), fast_Ring< TNum, kdefs >::createAdditionTable(), fast_Ring< TNum, kdefs >::createAdditiveInverseTable(), fast_Ring< TNum, kdefs >::createFastAdditionTable(), fast_Ring< TNum, kdefs >::createMultiplicationTable(), fast_Ring< TNum, kdefs >::createMultiplicativeInverseTable(), and fast_Ring< TNum, kdefs >::getGenerator().
const FieldType* fast_Ring< TNum, kdefs >::getField | ( | ) | const [inline] |
Definition at line 151 of file fast_Ring.h.
const FieldType& fast_Ring< TNum, kdefs >::getFieldRef | ( | ) | const [inline] |
Definition at line 156 of file fast_Ring.h.
TNum fast_Ring< TNum, kdefs >::getGenerator | ( | ) | [inline, protected] |
herausfinden, welchen Datentyp wir nach der -Operation haben und ob es Probleme bei unsigned Datentypen gibt.
vernuenftige Loesung fuer epsPrecision>0.
testen , ob angegebene Charakteristik eine Primzahl ist - Merkt man das nicht spaetestens wenn es keinen Erzeuger gibt?
Definition at line 781 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic(), and fast_Ring< TNum, kdefs >::getEpsPrecision().
int fast_Ring< TNum, kdefs >::getLookupModuloTableSize | ( | ) | const [inline] |
Definition at line 1136 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::moduloTableSize_m.
size_t fast_Ring< TNum, kdefs >::getMaxPairIndex | ( | ) | const [inline] |
Definition at line 1267 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
Referenced by fast_Ring< TNum, kdefs >::createAdditionTable(), and fast_Ring< TNum, kdefs >::createMultiplicationTable().
size_t fast_Ring< TNum, kdefs >::getMaxSingleIndex | ( | ) | const [inline] |
Definition at line 1259 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
Referenced by fast_Ring< TNum, kdefs >::createAdditiveInverseTable(), fast_Ring< TNum, kdefs >::createMultiplicativeInverseTable(), fast_Ring< TNum, kdefs >::createSqrtTable(), fast_Ring< TNum, kdefs >::initElementsToExponentsTab(), and fast_Ring< TNum, kdefs >::initExponentsToElementTab().
size_t fast_Ring< TNum, kdefs >::getPairIndex | ( | const TNum | z1, | |
const TNum | z2 | |||
) | const [inline] |
Definition at line 1289 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
Referenced by fast_Ring< TNum, kdefs >::accMult(), fast_Ring< TNum, kdefs >::accMultAddr(), fast_Ring< TNum, kdefs >::accMultRef(), fast_Ring< TNum, kdefs >::accMultSpec(), fast_Ring< TNum, kdefs >::add(), fast_Ring< TNum, kdefs >::addInPlace(), fast_Ring< TNum, kdefs >::createAdditionTable(), fast_Ring< TNum, kdefs >::createMultiplicationTable(), fast_Ring< TNum, kdefs >::multiply(), fast_Ring< TNum, kdefs >::multiplyInPlace(), fast_Ring< TNum, kdefs >::scalarMultiply(), and fast_Ring< TNum, kdefs >::scalarMultiplyInPlace().
size_t fast_Ring< TNum, kdefs >::getPairIndexByRef | ( | const TNum & | z1, | |
const TNum & | z2 | |||
) | const [inline] |
Definition at line 1296 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristicRef().
Referenced by fast_Ring< TNum, kdefs >::accMultRef(), fast_Ring< TNum, kdefs >::addInPlaceRef(), fast_Ring< TNum, kdefs >::addRef(), fast_Ring< TNum, kdefs >::multiplyInPlaceRef(), fast_Ring< TNum, kdefs >::multiplyRef(), fast_Ring< TNum, kdefs >::scalarMultiplyInPlaceRef(), and fast_Ring< TNum, kdefs >::scalarMultiplyRef().
size_t fast_Ring< TNum, kdefs >::getSingleIndex | ( | const TNum | z1 | ) | const [inline] |
Definition at line 1275 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
Referenced by fast_Ring< TNum, kdefs >::addInv(), fast_Ring< TNum, kdefs >::createAdditiveInverseTable(), fast_Ring< TNum, kdefs >::createMultiplicativeInverseTable(), fast_Ring< TNum, kdefs >::multInv(), and fast_Ring< TNum, kdefs >::multInvInPlace().
size_t fast_Ring< TNum, kdefs >::getSingleIndexByRef | ( | const TNum & | z1 | ) | const [inline] |
Definition at line 1283 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristicRef().
Referenced by fast_Ring< TNum, kdefs >::addInvInPlace(), fast_Ring< TNum, kdefs >::addInvRef(), and fast_Ring< TNum, kdefs >::multInvRef().
void fast_Ring< TNum, kdefs >::init | ( | ) | [inline, protected] |
Definition at line 35 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::additionTable, fast_Ring< TNum, kdefs >::additiveInverseTable, fast_Ring< TNum, kdefs >::createAdditionTable(), fast_Ring< TNum, kdefs >::createAdditiveInverseTable(), fast_Ring< TNum, kdefs >::createFastAdditionTable(), fast_Ring< TNum, kdefs >::createModuloTable(), fast_Ring< TNum, kdefs >::createMultiplicationTable(), fast_Ring< TNum, kdefs >::createMultiplicativeInverseTable(), fast_Ring< TNum, kdefs >::createSqrtTable(), fast_Ring< TNum, kdefs >::elementsToExponentsTab, fast_Ring< TNum, kdefs >::exponentsToElementTab, fast_Ring< TNum, kdefs >::fastAdditionTable, fast_Ring< TNum, kdefs >::generator, fast_Ring< TNum, kdefs >::initElementsToExponentsTab(), fast_Ring< TNum, kdefs >::initExponentsToElementTab(), fast_Ring< TNum, kdefs >::moduloTable, fast_Ring< TNum, kdefs >::multiplicationTable, fast_Ring< TNum, kdefs >::multiplicativeInverseTable, and fast_Ring< TNum, kdefs >::sqrtTable.
Referenced by fast_Ring< TNum, kdefs >::fast_Ring().
TNum * fast_Ring< TNum, kdefs >::initElementsToExponentsTab | ( | TNum | erzeuger | ) | [inline, protected] |
Definition at line 1045 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic(), and fast_Ring< TNum, kdefs >::getMaxSingleIndex().
Referenced by fast_Ring< TNum, kdefs >::init().
TNum * fast_Ring< TNum, kdefs >::initExponentsToElementTab | ( | TNum | erzeuger | ) | [inline, protected] |
Definition at line 1083 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic(), and fast_Ring< TNum, kdefs >::getMaxSingleIndex().
Referenced by fast_Ring< TNum, kdefs >::init().
bool fast_Ring< TNum, kdefs >::isValid | ( | TNum | a | ) | const [inline] |
Definition at line 190 of file fast_Ring.h.
References fast_Ring< TNum, kdefs >::Convert().
fast_Ring< TNum, kdefs >::FieldType::ElementType fast_Ring< TNum, kdefs >::lookupModuloTable | ( | int | convertee | ) | const [inline] |
Definition at line 1143 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::ConvertScalar(), fast_Ring< TNum, kdefs >::moduloTable, and fast_Ring< TNum, kdefs >::moduloTableSize_m.
TNum const fast_Ring< TNum, kdefs >::multByExp | ( | const TNum | a, | |
const TNum | b | |||
) | const [inline] |
Definition at line 516 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
void fast_Ring< TNum, kdefs >::multByExpInPlace | ( | TNum & | a, | |
const TNum | b | |||
) | const [inline] |
Definition at line 544 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
void fast_Ring< TNum, kdefs >::multByExpInPlaceRef | ( | TNum & | a, | |
const TNum & | b | |||
) | const [inline] |
Definition at line 558 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
TNum const fast_Ring< TNum, kdefs >::multByExpRef | ( | const TNum & | a, | |
const TNum & | b | |||
) | const [inline] |
Definition at line 530 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::getCharacteristic().
TNum fast_Ring< TNum, kdefs >::multInv | ( | const TNum | a | ) | const [inline] |
Definition at line 573 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getSingleIndex(), and fast_Ring< TNum, kdefs >::multiplicativeInverseTable.
void fast_Ring< TNum, kdefs >::multInvInPlace | ( | TNum & | a | ) | const [inline] |
Definition at line 617 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getSingleIndex(), and fast_Ring< TNum, kdefs >::multiplicativeInverseTable.
TNum fast_Ring< TNum, kdefs >::multInvRef | ( | const TNum & | a | ) | const [inline] |
Definition at line 592 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getSingleIndexByRef(), and fast_Ring< TNum, kdefs >::multiplicativeInverseTable.
TNum fast_Ring< TNum, kdefs >::multiply | ( | const TNum | a, | |
const TNum | b | |||
) | const [inline] |
Definition at line 396 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndex(), and fast_Ring< TNum, kdefs >::multiplicationTable.
void fast_Ring< TNum, kdefs >::multiplyInPlace | ( | TNum & | a, | |
const TNum | b | |||
) | const [inline] |
Definition at line 428 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndex(), and fast_Ring< TNum, kdefs >::multiplicationTable.
void fast_Ring< TNum, kdefs >::multiplyInPlaceRef | ( | TNum & | a, | |
const TNum & | b | |||
) | const [inline] |
Definition at line 439 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndexByRef(), and fast_Ring< TNum, kdefs >::multiplicationTable.
Referenced by fast_Ring< TNum, kdefs >::pow(), and fast_Ring< TNum, kdefs >::powInPlace().
TNum fast_Ring< TNum, kdefs >::multiplyRef | ( | const TNum & | a, | |
const TNum & | b | |||
) | const [inline] |
Definition at line 411 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndexByRef(), and fast_Ring< TNum, kdefs >::multiplicationTable.
TNum fast_Ring< TNum, kdefs >::pow | ( | TNum const | a, | |
unsigned int | exp | |||
) | const [inline] |
Definition at line 1211 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::multiplyInPlaceRef().
void fast_Ring< TNum, kdefs >::powInPlace | ( | TNum & | a, | |
unsigned int | exp | |||
) | const [inline] |
Definition at line 1235 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::multiplyInPlaceRef().
TNum fast_Ring< TNum, kdefs >::scalarMultiply | ( | const FieldType::ElementType | a, | |
const TNum | b | |||
) | const [inline] |
Definition at line 456 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndex(), and fast_Ring< TNum, kdefs >::multiplicationTable.
void fast_Ring< TNum, kdefs >::scalarMultiplyInPlace | ( | const FieldType::ElementType | a, | |
TNum & | b | |||
) | const [inline] |
Definition at line 489 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndex(), and fast_Ring< TNum, kdefs >::multiplicationTable.
void fast_Ring< TNum, kdefs >::scalarMultiplyInPlaceRef | ( | const FieldType::ElementType & | a, | |
TNum & | b | |||
) | const [inline] |
Definition at line 502 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndexByRef(), and fast_Ring< TNum, kdefs >::multiplicationTable.
TNum fast_Ring< TNum, kdefs >::scalarMultiplyRef | ( | const FieldType::ElementType & | a, | |
const TNum & | b | |||
) | const [inline] |
Definition at line 472 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), fast_Ring< TNum, kdefs >::getPairIndexByRef(), and fast_Ring< TNum, kdefs >::multiplicationTable.
void fast_Ring< TNum, kdefs >::setEpsPrecision | ( | int | epsPrecision | ) | const [inline] |
Definition at line 177 of file fast_Ring.h.
References fast_Ring< TNum, kdefs >::epsilon.
fast_Ring< TNum, kdefs >::sqrtInf_t fast_Ring< TNum, kdefs >::sqrt | ( | const TNum | a | ) | const [inline] |
Definition at line 740 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), and fast_Ring< TNum, kdefs >::sqrtTable.
Referenced by fast_Ring< TNum, kdefs >::createSqrtTable().
fast_Ring< TNum, kdefs >::sqrtInf_t fast_Ring< TNum, kdefs >::sqrtRef | ( | const TNum & | a | ) | const [inline] |
Definition at line 751 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::Convert(), and fast_Ring< TNum, kdefs >::sqrtTable.
bool fast_Ring< TNum, kdefs >::wellDefined | ( | ) | [inline] |
Definition at line 26 of file fast_Ring.cpp.
References fast_Ring< TNum, kdefs >::characteristic.
Referenced by fast_Ring< TNum, kdefs >::fast_Ring().
const TNum* fast_Ring< TNum, kdefs >::additionTable [private] |
Definition at line 132 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::accMult(), fast_Ring< TNum, kdefs >::accMultAddr(), fast_Ring< TNum, kdefs >::accMultRef(), fast_Ring< TNum, kdefs >::accMultSpec(), fast_Ring< TNum, kdefs >::add(), fast_Ring< TNum, kdefs >::addInPlace(), fast_Ring< TNum, kdefs >::addInPlaceRef(), fast_Ring< TNum, kdefs >::addRef(), fast_Ring< TNum, kdefs >::init(), and fast_Ring< TNum, kdefs >::~fast_Ring().
const TNum* fast_Ring< TNum, kdefs >::additiveInverseTable [private] |
Definition at line 130 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::addInv(), fast_Ring< TNum, kdefs >::addInvInPlace(), fast_Ring< TNum, kdefs >::addInvRef(), fast_Ring< TNum, kdefs >::init(), and fast_Ring< TNum, kdefs >::~fast_Ring().
const unsigned short fast_Ring< TNum, kdefs >::characteristic [private] |
Definition at line 118 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::createModuloTable(), fast_Ring< TNum, kdefs >::fast_Ring(), fast_Ring< TNum, kdefs >::getCharacteristic(), fast_Ring< TNum, kdefs >::getCharacteristicRef(), and fast_Ring< TNum, kdefs >::wellDefined().
const TNum* fast_Ring< TNum, kdefs >::elementsToExponentsTab [private] |
Definition at line 127 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::init(), and fast_Ring< TNum, kdefs >::~fast_Ring().
Definition at line 123 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::fast_Ring(), fast_Ring< TNum, kdefs >::getEpsPrecision(), and fast_Ring< TNum, kdefs >::setEpsPrecision().
const TNum* fast_Ring< TNum, kdefs >::exponentsToElementTab [private] |
Definition at line 128 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::init(), and fast_Ring< TNum, kdefs >::~fast_Ring().
const TNum* fast_Ring< TNum, kdefs >::fastAdditionTable [private] |
Definition at line 134 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::init(), and fast_Ring< TNum, kdefs >::~fast_Ring().
Definition at line 126 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::init().
const ScalarType* fast_Ring< TNum, kdefs >::moduloTable [private] |
Definition at line 136 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::init(), fast_Ring< TNum, kdefs >::lookupModuloTable(), and fast_Ring< TNum, kdefs >::~fast_Ring().
long fast_Ring< TNum, kdefs >::moduloTableSize_m [private] |
Definition at line 120 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::createModuloTable(), fast_Ring< TNum, kdefs >::getLookupModuloTableSize(), and fast_Ring< TNum, kdefs >::lookupModuloTable().
const TNum* fast_Ring< TNum, kdefs >::multiplicationTable [private] |
Definition at line 131 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::accMult(), fast_Ring< TNum, kdefs >::accMultAddr(), fast_Ring< TNum, kdefs >::accMultRef(), fast_Ring< TNum, kdefs >::accMultSpec(), fast_Ring< TNum, kdefs >::init(), fast_Ring< TNum, kdefs >::multiply(), fast_Ring< TNum, kdefs >::multiplyInPlace(), fast_Ring< TNum, kdefs >::multiplyInPlaceRef(), fast_Ring< TNum, kdefs >::multiplyRef(), fast_Ring< TNum, kdefs >::scalarMultiply(), fast_Ring< TNum, kdefs >::scalarMultiplyInPlace(), fast_Ring< TNum, kdefs >::scalarMultiplyInPlaceRef(), fast_Ring< TNum, kdefs >::scalarMultiplyRef(), and fast_Ring< TNum, kdefs >::~fast_Ring().
const TNum* fast_Ring< TNum, kdefs >::multiplicativeInverseTable [private] |
Definition at line 133 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::init(), fast_Ring< TNum, kdefs >::multInv(), fast_Ring< TNum, kdefs >::multInvInPlace(), fast_Ring< TNum, kdefs >::multInvRef(), and fast_Ring< TNum, kdefs >::~fast_Ring().
Definition at line 137 of file fast_Ring.h.
Referenced by fast_Ring< TNum, kdefs >::init(), fast_Ring< TNum, kdefs >::sqrt(), fast_Ring< TNum, kdefs >::sqrtRef(), and fast_Ring< TNum, kdefs >::~fast_Ring().