summaryrefslogtreecommitdiffstats
path: root/Objects/longobject.c
Commit message (Collapse)AuthorAgeFilesLines
...
* k_mul(): Heh -- I checked in two fixes for the last problem. Only keepTim Peters2002-08-121-2/+2
| | | | the good one <wink>. Also checked in a test-aid by mistake.
* k_mul(): White-box testing turned up that (ah+al)*(bh+bl) can, in rareTim Peters2002-08-121-3/+11
| | | | | | | | | cases, overflow the allocated result object by 1 bit. In such cases, it would have been brought back into range if we subtracted al*bl and ah*bh from it first, but I don't want to do that because it hurts cache behavior. Instead we just ignore the excess bit when it appears -- in effect, this is forcing unsigned mod BASE**(asize + bsize) arithmetic in a case where that doesn't happen all by itself.
* x_mul(): Made life easier for C optimizers in the "grade school"Tim Peters2002-08-121-4/+5
| | | | | | | | | | | | | | | | | | | | | | | | algorithm. MSVC 6 wasn't impressed <wink>. Something odd: the x_mul algorithm appears to get substantially worse than quadratic time as the inputs grow larger: bits in each input x_mul time k_mul time ------------------ ---------- ---------- 15360 0.01 0.00 30720 0.04 0.01 61440 0.16 0.04 122880 0.64 0.14 245760 2.56 0.40 491520 10.76 1.23 983040 71.28 3.69 1966080 459.31 11.07 That is, x_mul is perfectly quadratic-time until a little burp at 2.56->10.76, and after that goes to hell in a hurry. Under Karatsuba, doubling the input size "should take" 3 times longer instead of 4, and that remains the case throughout this range. I conclude that my "be nice to the cache" reworkings of k_mul() are paying.
* k_mul() and long_mul(): I'm confident that the Karatsuba algorithm isTim Peters2002-08-121-9/+30
| | | | | | | | correct now, so added some final comments, did some cleanup, and enabled it for all long-int multiplies. The KARAT envar no longer matters, although I left some #if 0'ed code in there for my own use (temporary). k_mul() is still much slower than x_mul() if the inputs have very differenent sizes, and that still needs to be addressed.
* k_mul: Rearranged computation for better cache use. Ignored overflowTim Peters2002-08-121-60/+50
| | | | | | | | | (it's possible, but should be harmless -- this requires more thought, and allocating enough space in advance to prevent it requires exactly as much thought, to know exactly how much that is -- the end result certainly fits in the allocated space -- hmm, but that's really all the thought it needs! borrows/carries out of the high digits really are harmless).
* x_mul(): This failed to normalize its result.Tim Peters2002-08-121-6/+18
| | | | | | | | | | | | | | | | | | | | | | k_mul(): This didn't allocate enough result space when one input had more than twice as many bits as the other. This was partly hidden by that x_mul() didn't normalize its result. The Karatsuba recurrence is pretty much hosed if the inputs aren't roughly the same size. If one has at least twice as many bits as the other, we get a degenerate case where the "high half" of the smaller input is 0. Added a special case for that, for speed, but despite that it helped, this can still be much slower than the "grade school" method. It seems to take a really wild imbalance to trigger that; e.g., a 2**22-bit input times a 1000-bit input on my box runs about twice as slow under k_mul than under x_mul. This still needs to be addressed. I'm also not sure that allocating a->ob_size + b->ob_size digits is enough, given that this is computing k = (ah+al)*(bh+bl) instead of k = (ah-al)*(bl-bh); i.e., it's certainly enough for the final result, but it's vaguely possible that adding in the "artificially" large k may overflow that temporarily. If so, an assert will trigger in the debug build, but we'll probably compute the right result anyway(!).
* Introduced helper functions v_iadd and v_isub, for in-place digit-vectorTim Peters2002-08-121-29/+75
| | | | | | | addition and subtraction. Reworked the tail end of k_mul() to use them. This saves oodles of one-shot longobject allocations (this is a triply- recursive routine, so saving one allocation in the body saves 3**n allocations at depth n; we actually save 2 allocations in the body).
* k_mul(): Repaired another typo in another comment.Tim Peters2002-08-121-1/+1
|
* k_mul(): Repaired typo in comment.Tim Peters2002-08-121-1/+1
|
* Cautious introduction of a patch that started fromTim Peters2002-08-121-85/+264
| | | | | | | | SF 560379: Karatsuba multiplication. Lots of things were changed from that. This needs a lot more testing, for correctness and speed, the latter especially when bit lengths are unbalanced. For now, the Karatsuba code gets invoked if and only if envar KARAT exists.
* staticforward bites the dust.Jeremy Hylton2002-07-171-1/+2
| | | | | | | | | | | | | | | The staticforward define was needed to support certain broken C compilers (notably SCO ODT 3.0, perhaps early AIX as well) botched the static keyword when it was used with a forward declaration of a static initialized structure. Standard C allows the forward declaration with static, and we've decided to stop catering to broken C compilers. (In fact, we expect that the compilers are all fixed eight years later.) I'm leaving staticforward and statichere defined in object.h as static. This is only for backwards compatibility with C extensions that might still use it. XXX I haven't updated the documentation.
* Undef MIN and MAX before defining them, to avoid warnings on certainGuido van Rossum2002-07-131-0/+2
| | | | platforms.
* Patch #568124: Add doc string macros.Martin v. Löwis2002-06-131-2/+2
|
* Clarify return value of PyLong_AsLongLong().Jeremy Hylton2002-04-231-1/+1
| | | | | | The function is documented to return -1 on error. If res was < 0, it returned res. It wasn't clear that the invariant was res < 0 iff res == -1.
* PyObject_Del can now be used as a function designator.Neil Schemenauer2002-04-121-1/+1
|
* Patch #494047: removes 64-bit ?: to cope on plan9.Martin v. Löwis2002-03-091-2/+10
|
* _PyLong_Copy(): was creating a copy of the absolute value, but shouldTim Peters2002-03-021-1/+1
| | | | | | copy the sign too. Added a test to test_descr to ensure that it does. Bugfix candidate.
* Patch #508038: Do not use a type as a variable name.Martin v. Löwis2002-02-161-3/+3
|
* long_true_divide(): decref its converted arguments. test_long_future.pyTim Peters2001-11-041-2/+5
| | | | | run in an infinite loop no longer grows. Thanks to Neal Norwitz for determining that test leaked!
* Enable GC for new-style instances. This touches lots of files, sinceGuido van Rossum2001-10-051-1/+2
| | | | | | | | | | | | | | | | | | | | | | many types were subclassable but had a xxx_dealloc function that called PyObject_DEL(self) directly instead of deferring to self->ob_type->tp_free(self). It is permissible to set tp_free in the type object directly to _PyObject_Del, for non-GC types, or to _PyObject_GC_Del, for GC types. Still, PyObject_DEL was a tad faster, so I'm fearing that our pystone rating is going down again. I'm not sure if doing something like void xxx_dealloc(PyObject *self) { if (PyXxxCheckExact(self)) PyObject_DEL(self); else self->ob_type->tp_free(self); } is any faster than always calling the else branch, so I haven't attempted that -- however those types whose own dealloc is fancier (int, float, unicode) do use this pattern.
* SF [#466125] PyLong_AsLongLong works for any integer.Tim Peters2001-09-301-1/+7
| | | | | | Generalize PyLong_AsLongLong to accept int arguments too. The real point is so that PyArg_ParseTuple's 'L' code does too. That code was undocumented (AFAICT), so documented it.
* Add additional coercion support for "self subtypes" to int, long,Guido van Rossum2001-09-191-0/+5
| | | | float (compare the recent checkin to complex). Added tests for these.
* A fix for SF bug #461546 (bug in long_mul).Guido van Rossum2001-09-151-10/+14
| | | | | | | | | Both int and long multiplication are changed to be more careful in their assumptions about when one of the arguments is a sequence: the assumption that at least one of the arguments must be an int (or long, respectively) is still held, but the assumption that these don't smell like sequences is no longer true: a subtype of int or long may well have a sequence-repeat thingie!
* based upon a suggestion in c.l.py, this slight expansion of theSkip Montanaro2001-09-131-1/+1
| | | | OverflowError message seems reasonable.
* long_invert(): tiny speed and space optimization.Tim Peters2001-09-111-2/+1
|
* More bug 460020. Disable a number of long optimizations for long subclasses.Tim Peters2001-09-111-18/+15
|
* SF bug #460020: bug or feature: unicode() and subclasses.Tim Peters2001-09-101-1/+20
| | | | | | | | | | | Given an immutable type M, and an instance I of a subclass of M, the constructor call M(I) was just returning I as-is; but it should return a new instance of M. This fixes it for M in {int, long}. Strings, floats and tuples remain to be done. Added new macros PyInt_CheckExact and PyLong_CheckExact, to more easily distinguish between "is" and "is a" (i.e., only an int passes PyInt_CheckExact, while any sublass of int passes PyInt_Check). Added private API function _PyLong_Copy.
* long_true_divide: reliably force underflow to 0 when the denominatorTim Peters2001-09-061-0/+2
| | | | | | has more bits than the numerator than can be counted in a C int (yes, that's unlikely, and no, I'm not adding a test case with a 2 gigabit long).
* Make the error msgs in our pow() implementations consistent.Tim Peters2001-09-051-3/+10
|
* Try to recover from that glibc's ldexp apparently doesn't set errno onTim Peters2001-09-051-2/+2
| | | | | overflow. Needs testing on Linux (test_long.py and test_long_future.py especially).
* Change long/long true division to return as many good bits as it can;Tim Peters2001-09-041-1/+32
| | | | e.g., (1L << 40000)/(1L << 40001) returns 0.5, not Inf or NaN or whatever.
* Move long_true_divide next to the other division routines (for clarity!).Tim Peters2001-09-041-6/+6
|
* Raise OverflowError when appropriate on long->float conversion. Most ofTim Peters2001-09-041-18/+19
| | | | | | | the fiddling is simply due to that no caller of PyLong_AsDouble ever checked for failure (so that's fixing old bugs). PyLong_AsDouble is much faster for big inputs now too, but that's more of a happy consequence than a design goal.
* Introduce new private API function _PyLong_AsScaledDouble. Not used yet,Tim Peters2001-09-041-0/+52
| | | | | | | | | | but will be the foundation for Good Things: + Speed PyLong_AsDouble. + Give PyLong_AsDouble the ability to detect overflow. + Make true division of long/long nearly as accurate as possible (no spurious infinities or NaNs). + Return non-insane results from math.log and math.log10 when passing a long that can't be approximated by a double better than HUGE_VAL.
* New restriction on pow(x, y, z): If z is not None, x and y must be ofTim Peters2001-09-031-3/+8
| | | | | integer types, and y must be >= 0. See discussion at http://sf.net/tracker/index.php?func=detail&aid=457066&group_id=5470&atid=105470
* Add warning mode for classic division, almost exactly as specified inGuido van Rossum2001-08-311-1/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | PEP 238. Changes: - add a new flag variable Py_DivisionWarningFlag, declared in pydebug.h, defined in object.c, set in main.c, and used in {int,long,float,complex}object.c. When this flag is set, the classic division operator issues a DeprecationWarning message. - add a new API PyRun_SimpleStringFlags() to match PyRun_SimpleString(). The main() function calls this so that commands run with -c can also benefit from -Dnew. - While I was at it, I changed the usage message in main() somewhat: alphabetized the options, split it in *four* parts to fit in under 512 bytes (not that I still believe this is necessary -- doc strings elsewhere are much longer), and perhaps most visibly, don't display the full list of options on each command line error. Instead, the full list is only displayed when -h is used, and otherwise a brief reminder of -h is displayed. When -h is used, write to stdout so that you can do `python -h | more'. Notes: - I don't want to use the -W option to control whether the classic division warning is issued or not, because the machinery to decide whether to display the warning or not is very expensive (it involves calling into the warnings.py module). You can use -Werror to turn the warnings into exceptions though. - The -Dnew option doesn't select future division for all of the program -- only for the __main__ module. I don't know if I'll ever change this -- it would require changes to the .pyc file magic number to do it right, and a more global notion of compiler flags. - You can usefully combine -Dwarn and -Dnew: this gives the __main__ module new division, and warns about classic division everywhere else.
* Ah, the joy of writing test cases...Guido van Rossum2001-08-301-1/+1
| | | | | long_subtype_new(): fix a typo (type->ob_size instead of tmp->ob_size).
* Make int, long and float subclassable.Guido van Rossum2001-08-291-2/+36
| | | | This uses a slightly wimpy and wasteful approach, but it works. :-)
* Patch #445762: Support --disable-unicodeMartin v. Löwis2001-08-171-0/+4
| | | | | | | | - Do not compile unicodeobject, unicodectype, and unicodedata if Unicode is disabled - check for Py_USING_UNICODE in all places that use Unicode functions - disables unicode literals, and the builtin functions - add the types.StringTypes list - remove Unicode literals from most tests.
* Implement PEP 238 in its (almost) full glory.Guido van Rossum2001-08-081-11/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | This introduces: - A new operator // that means floor division (the kind of division where 1/2 is 0). - The "future division" statement ("from __future__ import division) which changes the meaning of the / operator to implement "true division" (where 1/2 is 0.5). - New overloadable operators __truediv__ and __floordiv__. - New slots in the PyNumberMethods struct for true and floor division, new abstract APIs for them, new opcodes, and so on. I emphasize that without the future division statement, the semantics of / will remain unchanged until Python 3.0. Not yet implemented are warnings (default off) when / is used with int or long arguments. This has been on display since 7/31 as SF patch #443474. Flames to /dev/null.
* Merge of descr-branch back into trunk.Tim Peters2001-08-021-20/+75
|
* Python.h: Don't attempt to redefine NDEBUG if it's already defined.Tim Peters2001-07-151-1/+0
| | | | Others: Remove redundant includes of assert.h.
* long_format: Simplify the overly elaborate base-is-a-power-of-2 code.Tim Peters2001-07-151-28/+16
|
* divrem1 & long_format: found a clean way to factor divrem1 so thatTim Peters2001-07-141-28/+54
| | | | | long_format can reuse a scratch area for its repeated divisions (instead of malloc/free for every digit produced); speeds str(long)/repr(long).
* long_format(): Simplify new code a bit.Tim Peters2001-07-141-5/+8
|
* long_format(): Easy speedup for output bases that aren't a power of 2 (inTim Peters2001-07-131-9/+26
| | | | | | | particular, str(long) and repr(long) use base 10, and that gets a factor of 4 speedup). Another factor of 2 can be gotten by refactoring divrem1 to support in-place division, but that started getting messy so I'm leaving that out.
* On long to the negative long power, let float handle it instead ofGuido van Rossum2001-07-121-8/+7
| | | | | | raising an error. This was one of the two issues that the VPython folks were particularly problematic for their students. (The other one was integer division...) This implements (my) SF patch #440487.
* PyLong_{As, From}VoidPtr: cleanup, replacing assumptions in comments withTim Peters2001-06-161-15/+23
| | | | #if/#error constructs.
* Change IS_LITTLE_ENDIAN macro -- a little faster now.Tim Peters2001-06-141-1/+1
|
* _PyLong_AsByteArray: simplify the logic for dealing with the most-Tim Peters2001-06-141-11/+13
| | | | significant digits sign bits. Again no change in semantics.
generated by cgit v0.12 at 2024-10-23 16:24:15 (GMT)