Opened 11 years ago

Closed 11 years ago

#9652 closed defect (fixed)

Unnecesary and buggy code in arith.py

Reported by: mderickx Owned by: mderickx
Priority: minor Milestone: sage-4.6
Component: algebra Keywords:
Cc: mstreng, lftabera Merged in: sage-4.6.alpha1
Authors: Maarten Derickx Reviewers: Marco Streng, John Cremona, Luis Felipe Tabera
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by lftabera)

This code was added in #1148. I really think that the lines removed in my patch should be gone. The current (4.4.4) code is:

def valuation(m, p):
    if hasattr(m, 'valuation'):
        return m.valuation(p)
    if is_FractionFieldElement(m):  
        return valuation(m.numerator()) - valuation(m.denominator())
    if m == 0:
        import sage.rings.all
        return sage.rings.all.infinity
    r = 0
    power = p
    while not (m % power): # m % power == 0
        r += 1
        power *= p
    return r

Putting implementation specific to Fraction fields in a global function is bad practice. And since fraction fields have an implementation of valuation part of the above code will not be execucted. If it magicaly get's excecuted it will return bad results since it doesn't take into account the input variable "p" as it should.

Patches to apply in order:

  1. smallfix1-arith_valuation.2.3.patch
  1. smallfix1-arith_valuation-doctest.2.3.patch

Attachments (5)

smallfix1-arith_valuation.patch (1.4 KB) - added by mderickx 11 years ago.
smallfix1-arith_valuation.2.patch (4.7 KB) - added by mderickx 11 years ago.
Use this one, the other is an old version
smallfix1-arith_valuation.2.2.patch (4.7 KB) - added by mderickx 11 years ago.
Use this one, the other is an old version
smallfix1-arith_valuation.2.3.patch (4.5 KB) - added by lftabera 11 years ago.
previous patch with clenaer comment in the header
smallfix1-arith_valuation-doctest.2.3.patch (653 bytes) - added by lftabera 11 years ago.
additional doctest

Download all attachments as: .zip

Change History (36)

comment:1 Changed 11 years ago by mderickx

  • Status changed from new to needs_review

comment:2 Changed 11 years ago by mstreng

Two questions:

  • Is there any case in which any code after return infinity is executed and succesful?
  • Is there any case in which any code after return m.valuation(...) is executed and useful?

Can't you remove a lot more while you are at it? The code seems to be there to catch off weird unexpected cases that don't have a valuation attribute, but

  1. if the case is weird enough, then nothing guarantees that this function terminates
  2. if the case happens to have a negative valuation, then the function returns 0 instead of a negative number

While you are at it, I found that the function doesn't handle the valuation attribute of power series well (because it doesn't allow you to specify the (unique) prime p).

x = QQ[['x']].gen()
valuation(x^2, x)
TypeError: valuation() takes no arguments (1 given)
valuation(x^2)
TypeError: valuation() takes exactly 2 arguments (1 given)

The first error is because PowerSeries.valuation() takes no arguments; the second is because the global function takes exactly 2 arguments.

How about defining the global function simply as follows?

def valuation(m, *args1, **args2):
    return m.valuation(*args1, **args2)

or

def valuation(m, *args1, **args2):
    if m == 0:
        return sage.rings.all.infinity
    return m.valuation(*args1, **args2)

I haven't tried and/or ran any doctests with this, but anything that is broken by this isn't good coding practice, as you said :) Plus this fixes my example with valuation(x^2).

comment:3 Changed 11 years ago by mstreng

  • Cc mstreng added

comment:4 Changed 11 years ago by mderickx

I guess the code underneath there is for python integers, but I'm not sure. I will look into your questions when I have the time.

ps. similar practices seem to be going on a lot in arith.py I created a discussion on sage-devel. This discussion is not so much to discuss this specific example in detail, but to find a nice general solution for dealing with the problems involved when both using global functions an class methods to do the same thing.

I guess your remark about just passing all the aruments to the class method instead of having a static signature should be of value in that discussion also.

comment:5 Changed 11 years ago by mderickx

The code is indeed for python integers, and produces the right output in that case as the following shows.

sage: a=344r
sage: type(a)
<type 'int'>
sage: hasattr(a,"valuation")
False
sage: valuation(a,2)
3

I agree with you that that code should not be excecuted on general ring elements.

It crashes on local elements of the symbolic ring for example.

sage: var("z")
z
sage: valuation(z^2,z)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/Applications/sage/devel/sage-mderickx/<ipython console> in <module>()

/Applications/sage/local/lib/python2.6/site-packages/sage/rings/arith.pyc in valuation(m, p)
    604     r = 0
    605     power = p
--> 606     while not (m % power): # m % power == 0
    607         r += 1
    608         power *= p

TypeError: unsupported operand type(s) for %: 'sage.symbolic.expression.Expression' and 'sage.symbolic.expression.Expression'

.

In your remark 2. The code could also crash, for example try (1/2) % 2. I tried to find some real examples in sage, but I can't seem to find how to localize rings in sage. Maybe it's not implemented yet. The only thing I could find is: http://www.sagemath.org/doc/reference/coercion.html#example.

My failing quest to find other examples than python integers lead me to believe that this code should indeed only be excecuted on python integers.

comment:6 Changed 11 years ago by mstreng

Ah yes, python integers. Then perhaps first test if m is a python integer and call Integer(m).valuation(*args1, **args2) if it is and m.valuation(*args1, **args2) otherwise. I think you should leave out the m == 0 check because nobody wants valuation(0, 0) or valuation(0, 'whatever') to give any output.

comment:7 Changed 11 years ago by mstreng

valuation(int(1), int(1)) goes into an infinite loop

comment:8 Changed 11 years ago by mderickx

Ok so the code behaves buggy for valuation(1r,1r). I really think we should just let sage integers handle it. I really don't like having unneccery double code. Especially if one of the two is buggy.

By the way, the problem with valuation(0r,0r) is not just a problem of this code, it also happes with valuation on sage ints. Should we report that as a bug?

sage: 0.valuation(0)
+Infinity
sage: 8.valuation(0)
ValueError                                Traceback (most recent call last)
...
ValueError: You can only compute the valuation with respect to a integer larger than 1.

ps. if you want a number to not be converted to a sage integer by the preparser you should just put an r behind the number. Or else the preparser will generate the following silly code:

sage: preparse("valuation(int(1),int(1)")
'valuation(int(Integer(1)),int(Integer(1))'

What you want is this:

sage: preparse("valuation(1r,1r)")
'valuation(1,1)'

Changed 11 years ago by mderickx

comment:9 Changed 11 years ago by cremona

  • Status changed from needs_review to needs_work

You have added the extra arguments but have not documented them, or given any examples where they might be used. That's not good!

For the main code, why not do

try:
  return m.valuation(p)
except AttributeError:
   pass
try:
   return Integer(m).valuation(Integer(p))
except (something):
   raise an error

comment:10 Changed 11 years ago by mstreng

Wasn't the whole point of the extra arguments *args1, args2 to make the global function valuation also work for power series? It doesn't in the current Sage, and it wouldn't with John's suggestion, but actually, it also doesn't with Maarten's patch.

To make it work, remove p. That is, replace "p,*args1, **args2" by "*args1, **args2" or simply "*args1" both times it occurs in your patch.

In the EXAMPLES block, you could add

sage: y = QQ['y'].gen()
sage: valuation(y^3, y)
3
sage: x = QQ[['x']].gen()
sage: valuation(x^2)
2

This doesn't really belong to the topic of this patch, but as you are rewriting the function anyway...

comment:11 Changed 11 years ago by cremona

That looks better!

comment:12 Changed 11 years ago by mderickx

  • Status changed from needs_work to needs_review

I added a second patch which takes most of the comments into account. (please only apply the second patch, it got added as a second patch since I forgot to check the "replace existing file" box).

I didn't do anything with the "For the main code, why not do:" suggestion since to me it seemed to do the same thing but then with a different coding style. (My version is the "look before you leap version", and yours the "Easier to ask for forgiveness than permission."). If there are reasons to chose one above the other I would certainly do that. I know that my code will raise an attribute error sometimes, an error that you would rewrite in your case. But I guess that error should be not confusing at all to the enduser.

sage: valuation(graphs.!PetersenGraph())

---------------------------------------------------------------------------

!AttributeError                            Traceback (most recent call last)

/Users/maarten/<ipython console> in <module>()

/Applications/sage/local/lib/python2.6/site-packages/sage/rings/arith.pyc in valuation(m, *args1, **args2)

    600     if isinstance(m,(int,long)):

    601         m=Integer(m)

--> 602     return m.valuation(*args1, **args2)

    603 

    604 def prime_powers(start, stop=None):

!AttributeError: 'Graph' object has no attribute 'valuation'

sage: 

comment:13 follow-ups: Changed 11 years ago by lftabera

  • Status changed from needs_review to needs_work

You have to import "Integer" somewhere in the code:

sage: a=int(3)
sage: valuation(a,2)
...
--> 695         m=Integer(m)
...
NameError: global name 'Integer' is not defined

Add a doctest that uses an 'int' as argument to check that the previous code will work.

In the documentation, it says that valuation os zero is +Infinity but valuation with respect to zero is an error. However:

sage: valuation(0,0)
+Infinity
sage: K=QQ['x']
sage: x=K.gen()
sage: valuation(x,K(0))
...
PariError
sage: valuation(K(0),K(0))
+Infinity

comment:14 follow-up: Changed 11 years ago by mstreng

Why do you let the code work for float, but not for RealNumber?? (I wouldn't let it work for float at all.)

comment:15 in reply to: ↑ 14 Changed 11 years ago by lftabera

Replying to mstreng:

Why do you let the code work for float, but not for RealNumber?? (I wouldn't let it work for float at all.)

Could you elaborate that? For me, the code fails for floats with an AttributeError? exception (as well as RealNumber?).

comment:16 Changed 11 years ago by mderickx

I talked with Marco (mstreng) in real live. And his comment should be ignored as it was based on something he misread.

comment:17 in reply to: ↑ 13 Changed 11 years ago by mderickx

  • Status changed from needs_work to needs_review

I added the import and doctest as lftabera suggested.

I didn't do anything with the comment about QQx? since I already changed the documentation of the global function to say that you really should look at the documentation of the attribute functions. And the behaviour you show is consistent with the documentation of the attribute function.

comment:18 Changed 11 years ago by lftabera

  • Status changed from needs_review to needs_work

I found the following doctest failures (4.5.2):

sage -t -long "devel/sage-devel/sage/quadratic_forms/count_local_2.pyx"
sage -t -long "devel/sage-devel/sage/quadratic_forms/quadratic_formcount_local_2.py"
sage -t -long "devel/sage-devel/sage/quadratic_forms/quadratic_form
local_density_congruence.py"
sage -t -long "devel/sage-devel/sage/quadratic_forms/quadratic_formlocal_representation_conditions.py"

all related with

AttributeError?: 'sage.rings.finite_rings.integer_mod.IntegerMod_int' object has no attribute 'valuation'

Also, in the code, you import Integers in the case of 'int' or 'float'. However, the local namespace of arith contains ZZ. I have checked and it is fastr to use ZZ(m) instead of importing Integer and using Integer(m). This is a corner case though.

comment:19 in reply to: ↑ 13 Changed 11 years ago by mderickx

Is there somewhere in the math literature a definition of what a valuation should be for "Ring of integers modulo n", cause the way it behaves right now in sage doesn't agree with my definition of what conditions a valuation should satisfy. If v is a valuation then in particular I would like to have v(a*b)=v(a)+v(b). But in sage right now you get the following:

sage: for i in R:

....: for j in R: ....: if not valuation(i,Integer(3))+valuation(j,Integer(3))==valuation(i*j,Integer(3)): ....: print i,j ....: 3 3 3 6 6 3 6 6

comment:20 Changed 11 years ago by mderickx

oops, now with the right formatting:

 sage: for i in R: 
....:     for j in R: 
....:         if not valuation(i,Integer(3))+valuation(j,Integer(3))==valuation(i*j,Integer(3)):
....:             print i,j
....:             
3 3
3 6
6 3
6 6

comment:21 Changed 11 years ago by mderickx

By the way: R=ZZ.quo(9)

comment:22 Changed 11 years ago by lftabera

I am afraid that there are quite a bit of algorithms in SAGE that deal with IntegerModInt? as plain Integer. The algorithms work, but you may fail to give a standar mathematical sense to them. This would be an example.

comment:23 Changed 11 years ago by mderickx

Ok, then i'll just move the relevant parts of the old code so it becomes an attribute function of IntegerModInt? together with a note section that sais that it's not a valuation in the mathematical sense.

comment:24 Changed 11 years ago by mderickx

  • Owner changed from AlexGhitza to mderickx

Changed 11 years ago by mderickx

Use this one, the other is an old version

comment:25 Changed 11 years ago by mderickx

  • Status changed from needs_work to needs_review

Ok, I moved the code, and the integer mod classes now also have a valuation attribute. All doctest should pass now when patching against 4.4.4 (sorry haven't updated in a while).

Changed 11 years ago by mderickx

Use this one, the other is an old version

Changed 11 years ago by lftabera

previous patch with clenaer comment in the header

Changed 11 years ago by lftabera

additional doctest

comment:26 Changed 11 years ago by lftabera

  • Status changed from needs_review to needs_info

Everything looks fine. Applies and passes doctest in 4.5.3

I have modified the header of the patch in smallfix1-arith_valuation.2.3.patch and I have added another patch with a new doctest regarding a previous issue that arrived before valuation(1r,1r) not terminating.

Since I have not touched the code, I fell I can give possitive review, but before doing so, mderickx, give me the OK for the change in the header of your patch.

comment:27 Changed 11 years ago by mderickx

  • Cc lftabera added

I'm ok with the changes. Hooray, my first patch got through :).

comment:28 Changed 11 years ago by lftabera

  • Description modified (diff)
  • Status changed from needs_info to needs_review

comment:29 Changed 11 years ago by lftabera

  • Status changed from needs_review to positive_review

comment:30 Changed 11 years ago by mpatel

  • Authors set to Maarten Derickx
  • Milestone set to sage-4.6
  • Reviewers set to Marco Streng, John Cremona, Luis Felipe Tabera

Please remember to update the "Author(s)" and "Reviewer(s)" fields.

comment:31 Changed 11 years ago by mpatel

  • Merged in set to sage-4.6.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.