[Python-checkins] r46904 - sandbox/trunk/decimal-c/_decimal.c
mateusz.rukowicz
python-checkins at python.org
Tue Jun 13 05:01:47 CEST 2006
Author: mateusz.rukowicz
Date: Tue Jun 13 05:01:44 2006
New Revision: 46904
Modified:
sandbox/trunk/decimal-c/_decimal.c
Log:
Real dividing now works and passes all tests, integer not yet implemented. Commented 2 functions causing sigsegv.
Modified: sandbox/trunk/decimal-c/_decimal.c
==============================================================================
--- sandbox/trunk/decimal-c/_decimal.c (original)
+++ sandbox/trunk/decimal-c/_decimal.c Tue Jun 13 05:01:44 2006
@@ -86,8 +86,33 @@
* when I say "digit" I mean digit between 0-9 (limb consists of LOG digits).
*/
+/* NOTE: there is a little inconcistency with size arguments, sometimes they
+ * say how many limbs, sometimes how many digits, it's going to change XXX*/
+
/* takes new_digits from self[], starting from start_at digit, *digits* not limbs */
/* returns digit after that we returned (useful for rounding) */
+
+/* just returns how many significant limbs */
+static long
+_limb_size(long *self, long limbs)
+{
+ while(!self[limbs-1] && limbs >1) limbs --;
+ return limbs;
+}
+
+/* just like binary <<, but base BASE not 2 */
+static void
+_limb_move_left(long *self, long limbs, long count)
+{
+ assert(count >= 0);
+ long i;
+ for (i = limbs - 1; i - count >= 0; i--)
+ self[i] = self[i-count];
+
+ for (i = count-1; i >= 0; i--)
+ self[i] = 0;
+}
+
static long
_limb_first_n_digits(long *self, long ndigits, long start_at, long *new, long new_digits)
{
@@ -216,6 +241,8 @@
static long
_limb_get_digit(long *self, long ndigits, long i)
{
+ if(i >= ndigits)
+ return 0;
long pos = ndigits - i - 1;
long limb = pos / LOG;
pos %= LOG;
@@ -228,6 +255,22 @@
return tmp%10;
}
+/* returns how many significant digits */
+static long
+_limb_size_s(long *self, long size)
+{
+ long limbs = (size + LOG -1)/ LOG;
+ long slimbs;
+ slimbs = _limb_size(self, limbs);
+ long size_at_most = slimbs * LOG;
+
+ while(_limb_get_digit(self, size_at_most, 0) == 0 && size_at_most > 1) size_at_most --;
+
+ return size_at_most;
+
+}
+
+/* compares, self and other must be normalized */
static int
_limb_compare(long *self, long limbs, long *other, long olimbs)
{
@@ -241,6 +284,18 @@
return 0;
}
+/* just like above, but no need to proper sizes
+ * (may be extra zeros at most significant positions) */
+static int
+_limb_compare_un(long *self, long slimbs, long *other, long olimbs)
+{
+ long n_slimbs, n_olimbs;
+ n_slimbs = _limb_size(self, slimbs);
+ n_olimbs = _limb_size(other, olimbs);
+
+ return _limb_compare(self, n_slimbs, other, n_olimbs);
+}
+
static long
_limb_add_core(long *big, long bsize, long *small, long ssize, long *out)
{
@@ -286,6 +341,8 @@
return _limb_add_core(other, osize, self, ssize, out);
}
+/* substracts small from big, and stores result in out, sizes are in
+ * digits, not limbs */
static long
_limb_sub(long *big, long bsize, long *small, long ssize, long *out)
{
@@ -317,6 +374,29 @@
return left_digits;
}
+
+/* substracts small from big and stores result in big, sizes are in limbs
+ * returns how many limbs left */
+static long
+_limb_sub_sl(long *big, long blimbs, long *small, long slimbs)
+{
+ long i;
+ for(i = 0; i < slimbs; i++)
+ big[i] -= small[i];
+
+ for(i = 0; i < blimbs; i++) {
+ if (big[i] < 0)
+ {
+ assert(i + 1 < blimbs);
+ big[i] += BASE;
+ big[i+1] --;
+ }
+ }
+
+ return _limb_size(big, blimbs);
+
+
+}
/* temporary solution, will be speeded up */
static long
_limb_multiply_core(long *first, long flimbs, long *second, long slimbs, long *out)
@@ -371,6 +451,56 @@
return digits_at_most;
}
+/* performs dividing, returns relative position of dot to last limb, rest has
+ * at most as much elements as second + 1, it calculates prec *significant*
+ * limbs, first must not be 0 */
+/* XXX it's naive dividing, very slow */
+static long
+_limb_divide(long *first, long flimbs, long *second, long slimbs,
+ long *out, long prec, long *rest)
+{
+ long rlimbs = 1; /* significant limbs of rest */
+ long is_significant = 0; /* tells whether non_zero limb has already showed up */
+ long out_pos = prec - 1; /* where we write result starts at prec - 1 stops at 0*/
+ long new_pos = flimbs - 2; /* where is new digit to add at the end of rest,
+ if new_pos<0 add 0 */
+
+ rest[0] = first[flimbs-1];
+
+ while(1) {
+ long candidate = 0;
+ long cmp;
+
+ while ((cmp = _limb_compare_un(rest, rlimbs, second, slimbs)) >= 0) {
+ candidate ++;
+ rlimbs = _limb_sub_sl(rest, rlimbs, second, slimbs);
+ }
+
+ if (candidate)
+ is_significant = 1;
+
+ if (is_significant) {
+ out[out_pos] = candidate;
+ out_pos --;
+ }
+
+ if (out_pos < 0)
+ break;
+
+ assert(rlimbs <= slimbs +1);
+ _limb_move_left(rest, slimbs+1, 1);
+
+ if(new_pos >= 0)
+ rest[0] = first[new_pos];
+ else
+ rest[0] = 0;
+
+ rlimbs = _limb_size(rest, slimbs + 1);
+ new_pos --;
+ }
+
+ return new_pos;
+}
/* helpful macros ************************************************************/
@@ -2331,13 +2461,427 @@
return (PyObject*)_do_decimal_absolute(self, ctx, round);
}
+
+static PyObject *
+_do_decimal__divide(decimalobject *self, decimalobject *other, int divmod, contextobject *ctx)
+{
+ int sign = (self->sign&1) ^ (other->sign&1);
+ int self_is_zero;
+ int other_is_zero;
+ int shouldround;
+ PyObject *ans;
+
+ if (ISSPECIAL(self) || ISSPECIAL(other)) {
+ decimalobject *nan;
+ if (_check_nans(self, other, ctx, &nan)) {
+ if (divmod) {
+ ans = Py_BuildValue("(OO)", nan, nan);
+ Py_XDECREF(nan);
+ }
+ else
+ ans = (PyObject*) nan;
+
+ return ans;
+ }
+
+ if (ISINF(self) && ISINF(other)) {
+ if (divmod) {
+ decimalobject *ans1, *ans2;
+ ans1 = handle_InvalidOperation(self->ob_type, ctx,
+ "(+-) INF // (+-) INF", NULL);
+ if (!ans1)
+ return NULL;
+ ans2 = handle_InvalidOperation(self->ob_type, ctx,
+ "(+-) INF % (+-) INF", NULL);
+
+ if (!ans2) {
+ Py_DECREF(ans1);
+ return NULL;
+ }
+
+ ans = Py_BuildValue("(OO)", ans1, ans2);
+ Py_DECREF(ans1);
+ Py_DECREF(ans2);
+ }
+ else {
+ ans = (PyObject*)handle_InvalidOperation(self->ob_type, ctx,
+ "(+- INF / (+-) INF", NULL);
+ }
+
+ return ans;
+ }
+
+ if (ISINF(self)) {
+ decimalobject *inf;
+ int inf_sign;
+
+ inf_sign = sign ? SIGN_NEGINF : SIGN_POSINF;
+ inf = _NEW_decimalobj(1, inf_sign, 0);
+
+ if (!inf)
+ return NULL;
+
+ inf->limbs[0] = 0;
+
+ if (divmod == 1 || divmod == 3) {
+ decimalobject *ans2;
+
+ ans2 = handle_InvalidOperation(self->ob_type, ctx, "INF % x", NULL);
+ if (!ans2) {
+ Py_DECREF(inf);
+ return NULL;
+ }
+
+ ans = Py_BuildValue("(OO)", inf, ans2);
+
+ Py_DECREF(inf);
+ Py_DECREF(ans2);
+ }
+
+ else if (divmod == 2) {
+ decimalobject *nan;
+ nan = _NEW_decimalobj(1, SIGN_POSNAN, 0);
+ if (!nan) {
+ Py_DECREF(inf);
+ return NULL;
+ }
+ nan->limbs[0] = 0;
+
+ ans = Py_BuildValue("(OO)", inf, nan);
+ Py_DECREF(inf);
+ Py_DECREF(nan);
+ }
+ /* divmod == 0 */
+ else {
+ ans = (PyObject*) inf;
+ }
+
+ return ans;
+ }
+
+ if (ISINF(other)) {
+ if (divmod) {
+ decimalobject *ans1, *ans2;
+ ans1 = _NEW_decimalobj(1, sign, 0);
+
+ if (!ans1)
+ return NULL;
+
+ ans2 = _decimal_get_copy(self);
+ if (!ans2) {
+ Py_DECREF(ans1);
+ return NULL;
+ }
+
+ ans = Py_BuildValue("(OO)", ans1, ans2);
+ Py_DECREF(ans1);
+ Py_DECREF(ans2);
+ }
+ else {
+ decimalobject *ret;
+ if (handle_Clamped(ctx, NULL))
+ return NULL;
+
+ ret = _NEW_decimalobj(1, sign, ETINY(ctx));
+ if (!ret)
+ return NULL;
+ ret->limbs[0] = 0;
+ ans = (PyObject *) ret;
+ }
+
+ return ans;
+ }
+ }
+
+ self_is_zero = !decimal_nonzero(self);
+ other_is_zero = !decimal_nonzero(other);
+
+ if (self_is_zero && other_is_zero) {
+ if (divmod) {
+ return handle_DivisionUndefined(self->ob_type, ctx, "0 / 0", 1);
+ }
+ return handle_DivisionUndefined(self->ob_type, ctx, "0 / 0", 0);
+ }
+
+ if (self_is_zero) {
+ long exp;
+ if (divmod) {
+ decimalobject *ans1, *ans2;
+
+ ans2 = _decimal_get_copy(self);
+ if (!ans2)
+ return NULL;
+ ans2->exp = self->exp < other->exp ? self->exp : other->exp;
+
+ ans1 = _NEW_decimalobj(1, sign, 0);
+ if (!ans1) {
+ Py_DECREF(ans2);
+ return NULL;
+ }
+ ans = Py_BuildValue("(OO)", ans1, ans2);
+
+ Py_DECREF(ans1);
+ Py_DECREF(ans2);
+ return ans;
+ }
+
+ exp = self->exp - other->exp;
+
+ if (exp < ETINY(ctx)) {
+ exp = ETINY(ctx);
+ if (handle_Clamped(ctx, "0e-x / y"))
+ return NULL;
+ }
+
+ if (exp > ctx->Emax) {
+ exp = ctx->Emax;
+ if (handle_Clamped(ctx, "0e+x / y"))
+ return NULL;
+ }
+
+ {
+ decimalobject *ret;
+ ret = _NEW_decimalobj(1, sign, exp);
+ if (!ret)
+ return NULL;
+ ret->limbs[0] = 0;
+
+ ans = (PyObject*) ret;
+ return ans;
+ }
+
+ }
+
+ if (other_is_zero) {
+ if (divmod) {
+ return handle_DivisionByZero(self->ob_type, ctx, "divmod(x,0)", sign, 1);
+ }
+ return handle_DivisionByZero(self->ob_type, ctx, "x / 0", sign, 0);
+ }
+
+ /* now fun starts, answer isnt one of 0 NaN or INF */
+
+ shouldround = ctx->rounding_dec == ALWAYS_ROUND;
+
+ /* if we divide into ints, we'll check if self < other */
+ if (divmod) {
+ decimalobject *abs1, *abs2;
+ int cmp;
+ abs1 = _do_decimal_absolute(self, ctx, 0);
+ if (!abs1)
+ return NULL;
+
+ abs2 = _do_decimal_absolute(other, ctx, 0);
+ if (!abs2) {
+ Py_DECREF(abs1);
+ return NULL;
+ }
+
+ cmp = _do_real_decimal_compare(self, other, ctx);
+
+ Py_DECREF(abs1);
+ Py_DECREF(abs2);
+ if (PyErr_Occurred()) {
+ return NULL;
+ }
+
+ if (cmp == -1) {
+ decimalobject *ans1, *ans2;
+
+ ans1 = _NEW_decimalobj(1, sign, 0);
+ if (!ans1)
+ return NULL;
+ ans1->limbs[0] = 0;
+
+ if (divmod == 1 || divmod == 3) {
+ decimalobject *tmp;
+ long exp;
+ exp = self->exp < other->exp ? self->exp : other->exp;
+ tmp = _decimal_rescale(self, exp, ctx, -1, 0);
+
+ if (!tmp) {
+ Py_DECREF(ans1);
+ return NULL;
+ }
+
+ if (shouldround) {
+ ans2 = _decimal_fix(tmp, ctx);
+ if (!ans2) {
+ Py_DECREF(tmp);
+ Py_DECREF(ans1);
+ return NULL;
+ }
+ Py_DECREF(tmp);
+ }
+ else {
+ ans2 = tmp;
+ }
+
+ }
+
+ else if (divmod == 2) {
+ ans2 = _decimal_get_copy(self);
+ if (!ans2)
+ {
+ Py_DECREF(ans1);
+ return NULL;
+ }
+ }
+
+ ans = Py_BuildValue("(OO)", ans1, ans2);
+ Py_DECREF(ans1);
+ Py_DECREF(ans2);
+
+ return ans;
+ }
+ }
+
+
+ if (divmod == 0) {
+ long prec_needed; /* how many significant digits we need */
+ long significant_limbs; /* how many significant limbs we need to achieve prec */
+ decimalobject *result;
+ long *remainder;
+ long exp = self->exp - other->exp;
+ long expdiff;
+ long rlimbs;
+ long old_size;
+ long adj1, adj2, adjusted = 0;
+ long i;
+ long max_size;
+
+
+ if (!shouldround)
+ Py_RETURN_NONE; /* TODO */
+
+ prec_needed = ctx->prec+1;
+ /* we need (prec_needed + LOG -1)/ LOG rounded up limbs, because
+ * it may happen, that first limb is between 1 and 9, so we'll
+ * get (significant_limbs-1) * LOG + 1 digits */
+ significant_limbs = (prec_needed + LOG -1) / LOG;
+ significant_limbs += ((prec_needed + LOG -1) % LOG) != 0;
+
+ remainder = (long*) PyMem_MALLOC((other->limb_count+1) * sizeof(long));
+ memset(remainder, 0, sizeof(long) * (other->limb_count+1));
+ if (!remainder) {
+ PyErr_NoMemory();
+ return NULL;
+ }
+
+ /* we create room for additional limb, in case remainder != 0
+ * then, we will just move results->limbs one left, and set first
+ * limb 1, to make rounding working properly */
+ result = _NEW_decimalobj(significant_limbs * LOG + LOG, sign, 0);
+ for (i = 0; i < result->limb_count; i++)
+ result->limbs[0] = 0;
+ result->ob_size -= LOG;
+ result->limb_count --;
+ if (!result) {
+ PyMem_FREE(remainder);
+ return NULL;
+ }
+
+ expdiff = _limb_divide(self->limbs, self->limb_count,
+ other->limbs, other->limb_count, result->limbs,
+ significant_limbs, remainder);
+ result->limbs[significant_limbs] = 0;
+
+ exp += expdiff * LOG + LOG;
+
+ rlimbs = _limb_size(remainder, other->limb_count + 1);
+ /* non-zero */
+ if (!(rlimbs == 1 && remainder[0] == 0)) {
+ exp -= LOG;
+ result->limb_count ++;
+ result->ob_size += LOG;
+ _limb_move_left(result->limbs, result->limb_count, 1);
+ result->limbs[0] = 1;
+ }
+
+ old_size = result->ob_size;
+ result->ob_size = _limb_size_s(result->limbs, result->ob_size);
+ result->limb_count = (result->ob_size + LOG -1)/ LOG;
+
+ result->exp = exp;
+
+ max_size = self->ob_size > other->ob_size ? self->ob_size : other->ob_size;
+
+ /* adjusted is computed just like in the python code */
+ adjusted = self->ob_size - other->ob_size + 1;
+ for (i = 0;i < max_size ;i++) {
+ long x1,x2;
+ x1 = _limb_get_digit(self->limbs, self->ob_size, i);
+ x2 = _limb_get_digit(other->limbs, other->ob_size, i);
+ if (x2 > x1) {
+ adjusted --;
+ break;
+ }
+ }
+ assert(self->ob_size == _limb_size_s(self->limbs, self->ob_size));
+ assert(other->ob_size == _limb_size_s(other->limbs, other->ob_size));
+ /* to be compatible with python implementation, result int must
+ * have more than adjusted digits =] */
+
+
+ while (result->ob_size > adjusted &&
+ _limb_get_digit(result->limbs, result->ob_size, result->ob_size -1) == 0) {
+ _limb_cut_one_digit(result->limbs, result->ob_size);
+ result->ob_size --;
+ result->exp ++;
+ }
+
+
+
+ if (shouldround) {
+ decimalobject *fixed;
+ fixed = _decimal_fix(result, ctx);
+ Py_DECREF(result);
+ ans = (PyObject*) fixed;
+ }
+ else {
+ ans = (PyObject*) result;
+ }
+ PyMem_FREE(remainder);
+ return ans;
+ }
+
+ Py_RETURN_NONE;
+}
+
+static PyObject *
+decimal__divide(decimalobject *self, PyObject *args, PyObject *kwds)
+{
+ static char *kwlist[] = {"other", "divmod", "context", 0};
+ contextobject *ctx = NULL;
+ int divmod = 0;
+ PyObject *other;
+
+ if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|iO:_divide", kwlist,
+ &other, &divmod, &ctx))
+ return NULL;
+
+ if (!ctx)
+ if (!(ctx = getcontext()))
+ return NULL;
+
+ if (!PyDecimalContext_Check(ctx)) {
+ PyErr_SetString(PyExc_TypeError, "context must be Context object");
+ return NULL;
+ }
+
+ return (PyObject*) _do_decimal__divide(self, other, divmod, ctx);
+}
+
static PyMethodDef decimal_methods[] = {
+ {"_divide", (PyCFunction)decimal__divide,
+ METH_VARARGS | METH_KEYWORDS,
+ PyDoc_STR("TODO")},
{"_rescale", (PyCFunction)decimal_rescale,
METH_VARARGS | METH_KEYWORDS,
- PyDoc_STR("asdf")},
+ PyDoc_STR("asdf")}, /* TODO */
{"_fix", (PyCFunction)decimal_fix,
METH_VARARGS | METH_KEYWORDS,
- PyDoc_STR("asdf")},
+ PyDoc_STR("asdf")}, /* TODO */
{"adjusted", (PyCFunction)decimal_adjusted,
METH_NOARGS,
PyDoc_STR("Return the adjusted exponent of self.")},
@@ -2821,8 +3365,7 @@
_do_decimal_divide(decimalobject *self, decimalobject *other,
contextobject *ctx)
{
- /* XXX */
- Py_RETURN_NONE;
+ return _do_decimal__divide(self, other, 0, ctx);
}
DECIMAL_SPECIAL_2FUNC(decimal_divide)
@@ -2878,7 +3421,7 @@
static PyObject *
decimal_power(PyObject *self, PyObject *other, PyObject *modulo) {
- decimalobject *res;
+/* decimalobject *res;
contextobject *ctx = getcontext();
if (!ctx) return NULL;
@@ -2900,7 +3443,8 @@
ctx);
Py_DECREF(other);
Py_DECREF(modulo);
- return (PyObject *)res;
+ return (PyObject *)res;*/
+ Py_RETURN_NONE;
}
@@ -4284,7 +4828,7 @@
static PyObject *
context_power(contextobject *self, PyObject *args)
{
- PyObject *a, *b, *c;
+/* PyObject *a, *b, *c;
decimalobject *dec_a = NULL, *dec_b = NULL, *dec_c = NULL, *res;
if (!PyArg_ParseTuple(args, "OO|O:power", &a, &b, &c))
return NULL;
@@ -4311,7 +4855,8 @@
Py_DECREF(dec_a);
Py_DECREF(dec_b);
Py_DECREF(dec_c);
- return (PyObject *)res;
+ return (PyObject *)res;*/
+ Py_RETURN_NONE;
}
More information about the Python-checkins
mailing list