Fwd: Integer math

[Patrick Maupin]

Tried posting this at sympy group but hasn't gotten past the moderation yet.

Think sympycore might be a cleaner starting point anyway, after
looking at the code. Got confused, though, at the "Integers" that was
derived from "Set".

---------- Forwarded message ----------
From: Patrick Maupin <pma...@gmail.com>
Date: Thu, Jan 14, 2010 at 8:59 PM
Subject: Integer math
To: sympy <sy...@googlegroups.com>

Many years ago, in a universe far, far away, for a different employer,
I wrote a specialized symbolic algebra system in Python.  I need
something similar now, and am casting about to try to figure out how
hard it would be to tweak code from sympy or sympycore (or please feel
free to suggest other packages) to do what I need, or if I should just
write it all again.

Basically, I don't need (or want) real numbers or transcendental
functions or derivatives or any sort of fancy stuff like that.  I need
and want integers only, in the standard way that C and many other
computer and hardware languages deal with them.  This means that I
need simple algebra, bitwise operators, and logic operations.

In my world,  (2X + 6) / 4 is not at all the same as X/2 + 3/2.

But it is the same as (X+1) / 2 + 1, and ideally should have the same
canonical representation.

In my world, x && 3 can only evaluate to two possible answers, while x
& 3 can evaluate to four possible answers.  Likewise, x | 3 can
evaluate to (ideally, an infinite number of answers, but in reality,
and to quote Carl Sagan,) billions and billions of possible answers,
but there is only one answer for x || 3.

Some other things to consider:

(x - 5) && (23 * y)  is equivalent to (x != 5) * (y != 0)

(x - 5) || (23 * y)  is equivalent to ((x != 5)  + (y != 0)) != 0

x ? y : z   (or in new-fangled Python, y if x else z)  is equivalent
to (x!=0) * y + (x==0) * z

If memory serves, when I wrote a library like this before (almost a
decade ago when I was a Python newbie), it was just a few hundred
lines of code.   I've only looked at the sympy code a little, and
don't yet have a good understanding of where I would add this or how
large it would be to add -- the tradeoff of how much reuse I would
gain from the existing sympy code vs. the mental effort of learning
the system.

Any guidance on this would be greatly appreciated.

Best regards,
Pat

[Pearu Peterson]

Hi,

Patrick Maupin wrote:
> Tried posting this at sympy group but hasn't gotten past the moderation yet.
>
> Think sympycore might be a cleaner starting point anyway, after
> looking at the code. Got confused, though, at the "Integers" that was
> derived from "Set".

No. Integers is not derived from a Set, it is an instance of a Set:

Integers = Set(SYMBOL, 'Integers')

So, Integers is a set, not a constructor for constructing integer
numbers. Integers can be used in set operations. At the moment,
there is only one set predicate defined, that is, contains:

>>> Integers.contains('x')
Logic('(x) in Integers')

Integers was defined to support assumption system so that one
could have

some_simplify_method((a*b)**n, Integers.contains('n')) -> a**n * b**n

sympycore is designed to such applications, that is, support
defining new algebras with user defined properties and operations
with efficient data structure inherited from the Expr class.
The basic ideas are defined in

http://sympycore.googlecode.com/svn/trunk/doc/html/structure.html

See also sections 3 and 4 in

http://sympycore.googlecode.com/files/CSE09_pearu_slides.pdf

I'll try to cook up an example for your application to get you started..

Regards,
Pearu

[Patrick Maupin]

On Sat, Jan 16, 2010 at 3:12 AM, Pearu Peterson
<pearu.p...@gmail.com> wrote:
> Hi,

>
> Patrick Maupin wrote:
>
> No. Integers is not derived from a Set, it is an instance of a Set:
>
>  Integers = Set(SYMBOL, 'Integers')
>
> So, Integers is a set, not a constructor for constructing integer numbers.
> Integers can be used in set operations. At the moment,
> there is only one set predicate defined, that is, contains:
>
>>>> Integers.contains('x')
>    Logic('(x) in Integers')
>
> Integers was defined to support assumption system so that one
> could have
>
> some_simplify_method((a*b)**n, Integers.contains('n')) -> a**n * b**n
>

Ahh, that makes more sense.

...

>> Any guidance on this would be greatly appreciated.
>
> sympycore is designed to such applications, that is, support
> defining new algebras with user defined properties and operations
> with efficient data structure inherited from the Expr class.

Yes, that's what it looked like.

> The basic ideas are defined in
>
> http://sympycore.googlecode.com/svn/trunk/doc/html/structure.html
>
> See also sections 3 and 4 in
>
> http://sympycore.googlecode.com/files/CSE09_pearu_slides.pdf

Yes, I already read those, which is one of the reasons I mentioned
that it appeared that sympycore might be a better starting point\ than
sympy. The abstractions at the top look very elegant. But, when I
look at the code, it looks like it should be easy to do things at the
top, because a lot of complexity is pushed down at the bottom, but I
don't yet understand how to use the abstractions at the top.

> I'll try to cook up an example for your application to get you started..

That would be awesome. One thing, though, the more I think about it...

I don't think that what I need is too different from regular algebra.
In fact, I think it could be supported in the base calculus if you
fleshed out the support for floordiv() and added the ability to
intermix algebraic and logical operations. To start with, I don't
need all the potential optimizations. Some of those could be added as
I encounter them. But a basic system that understands a bit about
floor division and understands a bit about both logic and algebra
would be great.

Thanks in advance for any help you can provide.

Best regards,
Pat

[Patrick Maupin]

Almost forgot. In addition to logical operations and floordiv (and
complementary to floordiv), I need the modulo operation as well.

Thanks,
Pat

[Pearu Peterson]

Hi Pat,

I just commited a patch that supports

(2*x + 6)/4 -> (x+1)/2+1

evaluation. A small test script is given below.
To fully support your needs, some more coding
is needed. The example requires some improvements.
For example, the Integer class should define
algebra options, say, evaluate_integer_division
and the head classes in sympycore/heads should
interpret division operations appropriately.

Note that at the moment my time to work on sympycore
is quite limited but I'll try to answer any specific
questions you will have.

Regards,
Pearu

from sympycore import *
init_module.import_numbers()
init_module.execute()

class Integer(AdditiveAbelianGroup):

def __div__(self, other, inplace=False):
cls = type(self)
tother = type(other)
if tother is not cls:
if tother in numbertypes_set:
pass
other = cls.convert(other, typeerror=False)
if other is NotImplemented: return NotImplemented
return self.head.algebra_div(cls, self, other, inplace)

def _test():

x = Integer('x')
y = Integer('y')
n = Integer('3')

assert `x.pair`=="(SYMBOL, 'x')",`x.pair`
assert `n.pair`=="(NUMBER, 3)",`n.pair`
assert (2*x + 6) / 4==(x+1)/2+1,`(2*x + 6) / 4`

if __name__ == '__main__':

_test()

[Patrick Maupin]

That was quick!

Thanks so much for your support. I will have a play with this and
look at your patch to try to understand where further surgery is
required.

Best regards,
Pat

[Patrick Maupin]

BTW, I don't know if you saw my other email yet, but personally, I'm
perfectly happy to use the floordiv operator (python //)with
sympycore. Then, maybe at the end of the day, this is not a special
case algebra, but just works out of the box?

Thanks,
Pat

[Pearu Peterson]

Patrick Maupin wrote:
> BTW, I don't know if you saw my other email yet, but personally, I'm
> perfectly happy to use the floordiv operator (python //)with
> sympycore. Then, maybe at the end of the day, this is not a special
> case algebra, but just works out of the box?

Yes, I noticed that and I agree that FLOORDIV could be used
for implementing integer division. On the other hand,
DIV can be used to implement integer division with remainder,
which (6*x+2)/4->(x+1)/2+1 evaluation is actually using.
Well, this needs some playing..

Note that sympycore has a lot of obsolete but still working
code that I plan to reimplement. New development
should use sympycore/algebras and head classes should
define algebra_<op>(self, Algebra, lhs, rhs, inplace)
methods, in fact, there are many such methods not
implemented yet and actually Calculus is using the
corresponding obsolete methods.

Pearu