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