00001
00002
00003
00004 #include "arageli.h"
00005
00006 #ifndef POWEREST_H_
00007 #define POWEREST_H_
00008
00014
00015
00016 #ifndef __BORLANDC__
00017
00018
00020
00021
00022
00024 template <class monoid, class integer>
00025 monoid power(monoid a, integer n);
00026
00028 template <class integer_class>
00029 integer_class sqrt(const integer_class& x);
00030
00032 template <class integer_class>
00033 integer_class factorial(const integer_class& a);
00034
00036 template <class number_class>
00037 number_class absolute_value(const number_class& b);
00038
00040
00047 template <class euclid_ring_item>
00048 void quotient_remainder(euclid_ring_item a, euclid_ring_item b,
00049 euclid_ring_item& p, euclid_ring_item& r);
00050
00052 template <class euclid_ring_item>
00053 euclid_ring_item quotient(euclid_ring_item a, euclid_ring_item b);
00054
00056 template <class euclid_ring_item>
00057 euclid_ring_item remainder(euclid_ring_item a, euclid_ring_item b);
00058
00059 #endif // !defined(__BORLANDC__)
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074 template <class monoid, class integer>
00075 monoid power(monoid a, integer n)
00076 {
00077 int neg = n < 0;
00078 if (neg)
00079 n = -n;
00080 monoid res = 1;
00081 while (n != 0)
00082 {
00083 if (n % 2 != 0) res = res * a;
00084 a = a * a;
00085 n = n / 2;
00086 }
00087
00088 return res;
00089 }
00090
00091 template <class integer_class>
00092 integer_class sqrt(const integer_class& x)
00093 {
00094 if (x <= 0)
00095 return 0;
00096 else if (x == 1)
00097 return 1;
00098 else
00099 {
00100 integer_class r = x / 2;
00101 integer_class q;
00102 while(1)
00103 {
00104 q = x / r;
00105 if (q >= r)
00106 return r;
00107 else
00108 r = (r + q) / 2;
00109 }
00110 }
00111 }
00112
00113 template <class integer_class>
00114 integer_class factorial(const integer_class& a)
00115 {
00116 integer_class p = 1;
00117 for (integer_class i = 1; i <= a; i = i + 1)
00118 p = p * i;
00119 return p;
00120 }
00121
00122 template <class number_class>
00123 number_class absolute_value(const number_class& b)
00124 {
00125 if (b < number_class(0))
00126 return -b;
00127 else
00128 return b;
00129 }
00130
00131 template <class euclid_ring_item>
00132 void quotient_remainder(euclid_ring_item a, euclid_ring_item b,
00133 euclid_ring_item& p, euclid_ring_item& r)
00134 {
00135 r = a%b;
00136 p = a/b;
00137
00138 if (a < 0 && r != 0)
00139 {
00140 if (b > 0)
00141 p = p - 1;
00142 else
00143 p = p + 1;
00144 r = absolute_value(b) + r;
00145 }
00146 }
00147
00148 template <class euclid_ring_item>
00149 euclid_ring_item quotient(euclid_ring_item a, euclid_ring_item b)
00150 {
00151 euclid_ring_item p;
00152 euclid_ring_item r;
00153
00154 quotient_remainder(a, b, p, r);
00155
00156 return p;
00157 }
00158
00159 template <class euclid_ring_item>
00160 euclid_ring_item remainder(euclid_ring_item a, euclid_ring_item b)
00161 {
00162 euclid_ring_item p;
00163 euclid_ring_item r;
00164
00165 quotient_remainder(a, b, p, r);
00166
00167 return r;
00168 }
00169
00170 #endif //POWEREST_H_