> 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.
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
