Annotation of OpenXM/src/ox_ntl/ntl.cpp, Revision 1.1
1.1 ! iwane 1: /* $OpenXM$ */
! 2:
! 3: #include <NTL/ZZXFactoring.h>
! 4: #include <NTL/ZZ_pXFactoring.h>
! 5:
! 6: #include <iostream>
! 7: #include <strstream>
! 8:
! 9: #include "ntl.h"
! 10:
! 11:
! 12: /*==========================================================================*
! 13: * Check string format
! 14: *==========================================================================*/
! 15:
! 16: #define NtlIsSpace(c) ((c) == ' ' || (c) == '\t')
! 17: #define NtlIsDigit(c) ((c) >= '0' && (c) <= '9')
! 18:
! 19: /****************************************************************************
! 20: *
! 21: * test for string format of integer
! 22: *
! 23: * PARAM : I : str : string
! 24: * : O : endptr :
! 25: * RETURN: !0 : the string tests true
! 26: * : 0 : the string tests false
! 27: *
! 28: ****************************************************************************/
! 29: static int
! 30: ntl_isZZstr_(const char *str, char const **endptr)
! 31: {
! 32: while (NtlIsSpace(*str))
! 33: str++;
! 34:
! 35: /* NTL reject "+999" */
! 36: if (*str == '-')
! 37: str++;
! 38:
! 39: if (!NtlIsDigit(*str))
! 40: return (0);
! 41:
! 42: str++;
! 43:
! 44: while (NtlIsDigit(*str))
! 45: str++;
! 46:
! 47: *endptr = str;
! 48:
! 49: return (!0);
! 50:
! 51: }
! 52:
! 53: static int
! 54: ntl_isZZstr(const char *str)
! 55: {
! 56: const char *ptr;
! 57: int ret = ntl_isZZstr_(str, &ptr);
! 58: if (!ret)
! 59: return (ret);
! 60:
! 61: while (NtlIsSpace(*ptr))
! 62: ptr++;
! 63:
! 64: return (*ptr == '\0');
! 65: }
! 66:
! 67:
! 68: /****************************************************************************
! 69: *
! 70: * test for string format of univariate polynomials with integer coefficients
! 71: * in NTL style.
! 72: *
! 73: * PARAM : I : str : string
! 74: * : O : endptr :
! 75: * RETURN: !0 : the string tests true
! 76: * : 0 : the string tests false
! 77: *
! 78: ****************************************************************************/
! 79: static int
! 80: ntl_isZZXstr_(const char *str, char const **endptr)
! 81: {
! 82: const char *s;
! 83:
! 84: while (NtlIsSpace(*str))
! 85: str++;
! 86:
! 87: if (*str != '[')
! 88: return (0);
! 89:
! 90: str++;
! 91:
! 92: while (*str != ']' && *str != '\0') {
! 93:
! 94: if (!ntl_isZZstr_(str, &s))
! 95: return (0);
! 96: str = s;
! 97:
! 98: while (NtlIsSpace(*str))
! 99: str++;
! 100: }
! 101:
! 102: while (NtlIsSpace(*str))
! 103: str++;
! 104:
! 105: if (*str != ']')
! 106: return (0);
! 107:
! 108: str++;
! 109: *endptr = str;
! 110: return (!0);
! 111: }
! 112:
! 113: static int
! 114: ntl_isZZXstr(const char *str)
! 115: {
! 116: const char *ptr;
! 117: int ret = ntl_isZZXstr_(str, &ptr);
! 118: if (!ret)
! 119: return (ret);
! 120:
! 121: while (NtlIsSpace(*ptr))
! 122: ptr++;
! 123:
! 124: return (*ptr == '\0');
! 125: }
! 126:
! 127:
! 128: /*==========================================================================*
! 129: * Convert
! 130: *==========================================================================*/
! 131: static cmo_zz *
! 132: ZZ_to_cmo_zz(const ZZ &z)
! 133: {
! 134: cmo_zz *c;
! 135:
! 136: ostrstream sout;
! 137: sout << z << '\0';
! 138:
! 139: c = new_cmo_zz_set_string(sout.str());
! 140:
! 141: return (c);
! 142: }
! 143:
! 144:
! 145: static int
! 146: cmo_to_ZZ(ZZ &z, cmo *c)
! 147: {
! 148: int ret = NTL_SUCCESS;
! 149: char *str;
! 150:
! 151: switch (c->tag) {
! 152: case CMO_ZERO:
! 153: z = to_ZZ(0);
! 154: break;
! 155: case CMO_ZZ:
! 156: {
! 157: str = new_string_set_cmo(c);
! 158: istrstream sin(str, strlen(str));
! 159: sin >> z;
! 160: break;
! 161: }
! 162: case CMO_INT32:
! 163: z = to_ZZ(((cmo_int32 *)c)->i);
! 164: break;
! 165: case CMO_STRING:
! 166: {
! 167: str = ((cmo_string *)c)->s;
! 168: if (!ntl_isZZstr(str))
! 169: return (NTL_FAILURE);
! 170:
! 171: istrstream sin(str, strlen(str));
! 172: sin >> z;
! 173: break;
! 174: }
! 175: default:
! 176: ret = NTL_FAILURE;
! 177: break;
! 178: }
! 179:
! 180: return (ret);
! 181: }
! 182:
! 183:
! 184: static int
! 185: cmo_to_ZZX(ZZX &f, cmo *m, cmo_indeterminate *&x)
! 186: {
! 187: char *str;
! 188: int ret;
! 189:
! 190: switch (m->tag) {
! 191: case CMO_STRING: /* [ 3 4 7 ] ==> 3+4*x+7*x^2 */
! 192: str = ((cmo_string *)m)->s;
! 193: ret = 0; //ntl_isZZXstr(str);
! 194:
! 195: if (!ret) {
! 196: /* format error */
! 197: return (NTL_FAILURE);
! 198: }
! 199:
! 200: {
! 201: istrstream sin(str, strlen(str));
! 202: sin >> f;
! 203: }
! 204: break;
! 205: case CMO_RECURSIVE_POLYNOMIAL:
! 206: {
! 207: cmo_recursive_polynomial *rec = (cmo_recursive_polynomial *)m;
! 208: cmo_polynomial_in_one_variable *poly = (cmo_polynomial_in_one_variable *)rec->coef;
! 209: cell *el;
! 210: int len;
! 211:
! 212: if (poly->tag != CMO_POLYNOMIAL_IN_ONE_VARIABLE) {
! 213: return (NTL_FAILURE);
! 214: }
! 215:
! 216: el = list_first((cmo_list *)poly);
! 217: len = list_length((cmo_list *)poly);
! 218:
! 219: f = 0;
! 220:
! 221: while (!list_endof((cmo_list *)poly, el)) {
! 222: ZZ c;
! 223: ostrstream sout;
! 224: cmo *coef = el->cmo;
! 225: int exp = el->exp;
! 226:
! 227: ret = cmo_to_ZZ(c, coef);
! 228: if (ret != NTL_SUCCESS) {
! 229: return (NTL_FAILURE);
! 230: }
! 231:
! 232: SetCoeff(f, exp, c);
! 233:
! 234: el = list_next(el);
! 235: }
! 236:
! 237:
! 238: el = list_first(rec->ringdef);
! 239: x = (cmo_indeterminate *)el->cmo;
! 240:
! 241: break;
! 242: }
! 243: default:
! 244: break;
! 245: }
! 246: return (NTL_SUCCESS);
! 247: }
! 248:
! 249: /****************************************************************************
! 250: *
! 251: *
! 252: *
! 253: * PARAM : I : arg : polynomial
! 254: * : I : argc :
! 255: * RETURN: [[num, 1],[factor1,multiplicity1],[factor2,multiplicity2],...]
! 256: *
! 257: * EX :
! 258: *
! 259: ****************************************************************************/
! 260: static cmo_recursive_polynomial *
! 261: ZZX_to_cmo(ZZX &factor, cmo_indeterminate *x)
! 262: {
! 263: cmo_recursive_polynomial *rec;
! 264: cmo_polynomial_in_one_variable *poly;
! 265:
! 266: cmo_list *ringdef;
! 267: int i;
! 268: cmo *coef;
! 269:
! 270: ringdef = new_cmo_list();
! 271: list_append(ringdef, (cmo *)x);
! 272:
! 273: poly = new_cmo_polynomial_in_one_variable(0);
! 274: for (i = deg(factor); i >= 0; i--) {
! 275: if (coeff(factor, i) == 0)
! 276: continue;
! 277:
! 278: coef = (cmo *)ZZ_to_cmo_zz(coeff(factor, i));
! 279: list_append_monomial((cmo_list *)poly, coef, i);
! 280: }
! 281:
! 282: rec = new_cmo_recursive_polynomial(ringdef, (cmo *)poly);
! 283: return (rec);
! 284: }
! 285:
! 286:
! 287: static cmo_list *
! 288: new_cmo_pair_ZZX_int(ZZX &factors, int d, cmo_indeterminate *x)
! 289: {
! 290: cmo_recursive_polynomial *poly;
! 291: cmo_int32 *deg;
! 292: cmo_list *list;
! 293:
! 294: poly = ZZX_to_cmo(factors, x);
! 295: deg = new_cmo_int32(d);
! 296:
! 297: list = list_appendl(NULL, poly, deg, NULL);
! 298:
! 299: return (list);
! 300: }
! 301:
! 302:
! 303: /****************************************************************************
! 304: *
! 305: * convert vec_pair_ZZX_long(list of factor and multiplicity) to cmo_list
! 306: *
! 307: * PARAM : I : factors : list of factor and multiplicity
! 308: * : : : [[factor1,multiplicity1][factor2,multiplicity2]...]
! 309: * : I : x : indeterminate
! 310: * RETURN:
! 311: *
! 312: ****************************************************************************/
! 313: static cmo_list *
! 314: factors_to_cmo(vec_pair_ZZX_long &factors, cmo_indeterminate *x)
! 315: {
! 316: int i;
! 317: cmo_list *list = new_cmo_list();
! 318: cmo_list *factor;
! 319:
! 320: for (i = 0; i < factors.length(); i++) {
! 321: factor = new_cmo_pair_ZZX_int(factors[i].a, factors[i].b, x);
! 322: list_append(list, (cmo *)factor);
! 323: }
! 324:
! 325: return (list);
! 326: }
! 327:
! 328:
! 329: /****************************************************************************
! 330: *
! 331: * Factorize polynomial over the integers.
! 332: *
! 333: * PARAM : I : arg : polynomial
! 334: * : I : argc :
! 335: * RETURN: [num,[[factor1,multiplicity1],[factor2,multiplicity2],...]]
! 336: *
! 337: * EX : ntl_fctr([2*x^11+4*x^8-2*x^6+2*x^5-4*x^3-2],1) ==>
! 338: : [2,[[x-1,1],[x^4+x^3+x^2+x+1,1],[x+1,2],[x^2-x+1,2]]]
! 339: *
! 340: ****************************************************************************/
! 341: cmo *
! 342: ntl_fctr(cmo **arg, int argc)
! 343: {
! 344: cmo *poly = arg[0];
! 345: cmo_indeterminate *x;
! 346: ZZX f;
! 347: ZZ c;
! 348:
! 349: int ret;
! 350:
! 351: vec_pair_ZZX_long factors;
! 352:
! 353: cmo_list *ans;
! 354: cmo *fcts;
! 355:
! 356: if (argc != 1) {
! 357: return ((cmo *)new_cmo_error2((cmo *)new_cmo_string("Invalid Parameter(#)")));
! 358: }
! 359:
! 360: ret = cmo_to_ZZX(f, poly, x);
! 361: if (ret != NTL_SUCCESS) {
! 362: /* format error */
! 363: return ((cmo *)new_cmo_error2((cmo *)new_cmo_string("Invalid Parameter(type)")));
! 364: }
! 365:
! 366: factor(c, factors, f);
! 367:
! 368: cmo_zz *zz = ZZ_to_cmo_zz(c);
! 369:
! 370: ans = new_cmo_list();
! 371:
! 372: fcts = (cmo *)factors_to_cmo(factors, x);
! 373:
! 374: list_appendl(ans, zz, (cmo *)fcts, NULL);
! 375:
! 376: return ((cmo *)ans);
! 377: }
! 378:
! 379:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>