[Tutor] Actual code that illustrates problem
Danny Yoo
dyoo at hkn.eecs.berkeley.edu
Thu Aug 17 18:57:40 CEST 2006
> To try to find factors of z, using w.
>
>>>>
>
> * What are the inputs? What is 'z', and what is 'w'?
>
> ******
>
> z is the number to be factores.
>
> w is a "witness", a number that may help find the factors of z.
[My apologies in advance; this message is a bit long.]
Hi Kermit,
Ok, good. You should add this as a comment to the function's header, so
that other people can see this. Here is an example:
def strongfac(z, w):
"""z is the number to be factored.
w is a witness that may help find the factors of z.
"""
## rest of function body.
At the very beginning of the function body, we're allowed to make a string
that acts as function documentation. Python programmers expect this kind
of "documentation string" at the head of a function, so that they're
prepared for what comes next.
> * What are the outputs? What is the return value of strongfac?
>
> The output is the return value of strongfac.
> fac = [ x, y, difficulty of factoring z using w]
> or
> fac = [0,0,0] if strongfac could not factor z using w.
Great! Ok, I'm assuming that 'x' and 'y' are two arbitrary factors of
'z'. Are there other properties about x and y that you want to state,
such as: "x is always prime", or do we make no guarantees about this?
At this point, I'm distilling what you've said into a documentation
string:
def strongfac(z, w):
"""strongfac: number number -> [x, y, difficulty]
Factors z into two pieces, returning those two pieces as well as the
difficulty in factoring z. w is a witness that may help find the
factors of z.
If no factors can be found, returns [0, 0, 0].
"""
## rest of function body.
Does this make sense so far? The point is to make it easy for humans to
understand your program.
>> # face = [x,y,0]
> [some code cut]
>> # face[0] = x
>> # face[1] = y
>> # face[2] = 0
>
>> The three assignments to face[0] through face[2] don't do anything
>> effective and clutter the code.
>
> In fact, I knew that. I inserted it in an attempt to overide the
> apparent bug that I saw.
>
> Sometimes it worked.
This is a bad sign. It should not have worked. *grin*
Next time you hit something mysterious like this, mention it to the list.
It'll be a good puzzle for the others here to take a look at. Your code
should be as rational as possible. Don't just add code in hoping that
it'll fix some problem: try to understand why it's not working first.
Look for root causes.
>> In fermat(), there are magic numbers:
> [cut]
>> These seem pretty arbitrary. Can you explain them?
> Yes. These are limits of ranges. I had not yet evolved the module to
> replace the range limits with parameters.
About strongfac():
> Have you considered breaking those out as independent helper functions?
>
> I have considered it.
Consider it more strongly. *grin*
Here, I'll help you get started. strongfac() starts off looking something
like this:
#################################################################
def strongfac(z,w):
x = gcd(z,w-1)
if x > 1:
if x < z:
y = z/x
return [x,y,0]
w2 = (w * w)%z
s = ksqrt(w2)
if w2 == s * s:
if s != w:
x = gcd(z,kabs(w2 - s))
if x > 1:
if x < z:
return [x,y,0]
## other tests
################################################################
(I'm trimming out the print statements just to keep this small.)
Those two tests, the P-1 and square=square tests, can be broken out into
two separate functions. Let's see what this might look like:
############################################################
def check_p_minus_1(z, w):
"""Checks to see if z can be factored by the P-1 Method.
If so, returns [x, y, 0]; otherwise, returns [0, 0, 0].
"""
x = gcd(z,w-1)
if x > 1:
if x < z:
y = z/x
return [x,y,0]
return [0, 0, 0]
############################################################
This "refactoring" allows us to look at check_p_minus_1's action in
isolation, and also makes it easier to ask questions like: what happens if
x > z? Is it really possible that the return value from gcd() is bigger
than the initial inputs to gcd()? (As far as I understand gcd(), NO!)
So this refactoring is useful just as a matter of letting someone just
look at a small bit of code and understand it completely. As far as I can
understand, check_p_minus_1() should work even if it's simplified to:
##########################
def check_p_minus_1(z, w):
x = gcd(z, w-1)
if x != 1:
return [x, z/x, 0]
return [0, 0, 0]
##########################
Anyway, once we break out the P-1 check out into a separate function, we
can rewrite strongfac() to use check_p_minus_1():
################################
def strongfac(z, w):
face = check_p_minus_1(z, w)
if face != [0, 0, 0]:
return face
## ... other tests here
################################
Can you try this? Can you try breaking out the square=square test in a
similar way to how I treated the check_p_minus_1() code?
The high level goal here is to turn strongfac() into a very simple looking
function. In pseudocode, it'll look something like:
############################
def strongfac(z, w):
use check_p_minus_1 test and return if it succeeds
use square=square test and return if it succeeds
...
############################
This will make strongfac very regular to read. It'll also make it much
easier to trace why one of your return values isn't returning what you
want.
More information about the Tutor
mailing list