# def strongfac(z,w):
[function body cut]

, let's go through this step by step.

* What is the intent of strongfac?
* What are the inputs? What is 'z', and what is 'w'?
* What are the outputs? What is the return value of strongfac?

Same questions for fermat(). What are the inputs and outputs, and what's
the intent?

Get those out and documented, because although I think I can guess at it,
I'd rather know that we are sharing the same understanding.

There's a bit of code in strongfac() that's nonsensical from a purely
technical sense. For example:

# 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 fermat(), there are magic numbers:

# for j in range(2,3):
^^^^

# for k in range(100):
^^^

These seem pretty arbitrary. Can you explain them?

The strongfac() function you have is a good case for writing smaller
functions: I can not tell where the function really ends. I see that you
have several sub-tests, which I'll categorize as:

* P-1
* square = square
*

and there's a few others that I can not categorize yet. But I bet you
can. Have you considered breaking those out as independent helper
functions?

Most of us don't have experience with number theory. What people here on
the list have is experience with writing software. My experience informs
me that the functions you're writing are way too large. They are
monolithic and imposing enough that very few people will be able to (or
want to!) understand their reasoning. They really cry out to be broken
into smaller subtest functions that can be individually understood.

(And even if your program were running perfectly well, I'd still strongly
recommend you practice the skill of small, easy-to-understand functions.)

You mentioned later that:

of the numbers for which strongfac fails to return factors which it
correctly calculates is 100000000000037

Two questions:

* How do you know that it is being "correctly calculated?"

* How do you know that your program is doing something wrong?

That is, state explicitely to us what you expected the program to do.
What is the expected result, in terms of return values, that your function
failed to produce? What part of the program which particular subtest
should have returned those values? Where are you looking at?

Again, you have to assume that we don't know anything about number theory.
Things that may seem "obvious" to you are not obvious to this audience.
*grin*

Tutor maillist - Tutor (AT) python (DOT) org

From: Danny Yoo
Date: 08/17/06 04:02:35
To: Kermit Rose
Cc: Tutor
Subject: Re: [Tutor] Actual code that illustrates problem

# def strongfac(z,w):
[function body cut]

, let's go through this step by step.

* What is the intent of strongfac?

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.

* 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.

Same questions for fermat(). What are the inputs and outputs, and what's
the intent?

The input z is the number to be factored.

The other inputs are constants which may help in finding factors of z.

Get those out and documented, because although I think I can guess at it,
I'd rather know that we are sharing the same understanding.

?

How?

There's a bit of code in strongfac() that's nonsensical from a purely
technical sense. For example:

# 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.

In fermat(), there are magic numbers:

# for j in range(2,3):
^^^^

# for k in range(100):
^^^

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.

The strongfac() function you have is a good case for writing smaller
functions: I can not tell where the function really ends. I see that you
have several sub-tests, which I'll categorize as:

* P-1
* square = square
*

and there's a few others that I can not categorize yet. But I bet you
can. Have you considered breaking those out as independent helper
functions?

I have considered it.

Most of us don't have experience with number theory. What people here on
the list have is experience with writing software. My experience informs
me that the functions you're writing are way too large. They are
monolithic and imposing enough that very few people will be able to (or
want to!) understand their reasoning. They really cry out to be broken
into smaller subtest functions that can be individually understood.

Luke has promised to work with me to write my module as a class.

Perhaps this will automatically shorten the individual functions.

I don't expect that you would need to know much number theory to understand
what my program is doing, but I'll be glad to answer any question you may
have of it.

You mentioned later that:

of the numbers for which strongfac fails to return factors which it
correctly calculates is 100000000000037

Two questions:

* How do you know that it is being "correctly calculated?"

Part of the process of finding any factor is to divide it into z to get
remainder equal to zero.

Also when I noticed the problem, I printed it out in strong fac, and also in
fermat
and then saw the strange behavior of having one value before return
and another value after return.

* How do you know that your program is doing something wrong?

That is, state explicitely to us what you expected the program to do.
What is the expected result, in terms of return values, that your function
failed to produce? What part of the program which particular subtest
should have returned those values? Where are you looking at?

I first noticed it when I had

Strong fac calculate the factors if possible. If it found factors,

it printed out that it had found factors using w, and it printed the value
of w.

After I noticed that strongfac printed out that it had found factors, but
fermat
did not pick up those factors, I looked more closely.

After I had documented to myself that the return value had changed by the
time it got back
to fermat, I emailed the Tutor list.

Again, you have to assume that we don't know anything about number theory.
Things that may seem "obvious" to you are not obvious to this audience.
*grin*

So noted. I had not intended to ask any number theory questions here.

Kermit < kermit (AT) polaris (DOT) net >

Tutor maillist - Tutor (AT) python (DOT) org

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,

, 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! , 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(), N!)

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 - Tutor (AT) python (DOT) org

Danny Yoo wrote:
--
Hi Kermit,

, 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.

I've added the suggested documentation for strongfac.

>
>* 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! , 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?
--
Yes. That is correct. There is not any expectation that x and y would
be prime unless z just happens to be the product of exactly two primes.

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.
--

Yes. I've replaced the previously suggested documentation with the above.

# 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.
--
I agree. I reasoned as follows.

The root cause is that Python is not returning the correct value of a list.

So before I return the list, I will remind Python what's in the list.

About strongfac():
>
>
>
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?
>
>
>

I have followed your suggestion and have done so.

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.
you want.

I will work on splitting up the rest of strong fac into a set of
functions.

I will attempt to maintain a compromise between having too many levels
of function calls and
having any one function be too long.

Kermit < kermit (AT) polaris (DOT) net >

Tutor maillist - Tutor (AT) python (DOT) org

# face = [x,y,0]
[some code cut]
# face[0] = x
# face[1] = y
# face[2] = 0

I agree. I reasoned as follows.

The root cause is that Python is not returning the correct value of a list.

So before I return the list, I will remind Python what's in the list.

Hi Kermit,

Let's take those last three assignments out: they don't do anything as far
as I can see. If you do see a functional change in your program after
doing so, I'll be very surprised and intrigued. *grin*

The reason for taking them out is to, again, make the program as short
and sweet as we can for humans to read. A program's readability matters.

I will work on splitting up the rest of strong fac into a set of
functions.

That sounds good! Definitely keep us up-to-date while you do it. We can
give suggestions if we see something that can be simplified, and we want
to make sure you don't run into any big ruts as you do this.

your program is in smaller functional chunks, let's look again at
your original problem. I'm hoping that it'll be easier to chase the
problem down then.

I will attempt to maintain a compromise between having too many levels
of function calls and having any one function be too long.

I wouldn't worry about having heavy function call depth too much yet. If
it does turn out to be an issue, reversing the refactoring by inlining
should be mechanically easy to do.

Good luck to you!

Tutor maillist - Tutor (AT) python (DOT) org

While others have made good suggestions to clarify the code I thought
I'd try to tackle the question of whether we had a bug in Python.

Unfortunately the debug output does not come from the code that's
posted so its difficult to figure out what's been happening.

For example, one apparently good and one "faulty" test:

In strongfac
Found1: x = 53799857
Found1: y = 1858741
face = [53799857L, 1858741L, 0]
Found1: factor by strong probable prime test, using witnes
15306543515214

Note the mis-spelling of witnes(sic) - it does not appear in the code!

Found1: factors are 53799857 1858741
Found1: returning [53799857L, 1858741L, 0] to fermat routine.
Retrieved from strongfac, face = [0, 0, 0]
In fermat: k = 13 x = 0 y = 0 face = [0, 0, 0]

Similarly the first line has the text "factors are 53"

But in the code all instances of "factors are" are followed by the
word "by"

So I conclude the tests are not from this code. The fault may be in
this code
but I can't be sure

However a couple of observations might help:

# def strongfac(z,w):
# x = gcd(z,w-1)
# if x 1:
# if x < z:

You can simpliffy this 2 stage test using either boolean operartors:

if x 1 and x < z:

R, almost uniquie to pyhon:

if 1 < x < z:

That removes one whole layer of indentation.
This trick can be applied in many places in the algorithm.

Also

# y = z/x
# print "Found factors by P-1 Method as part of
Strong
probable prime test, using witness",w,"."
# print " x = ",x," y = ",y
# 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:
# print "Found factors by square = square as
part of
Strong probable prime test, using witness",w,"."
# return [x,y,0]

If x was not between 1 and z in the first test y is not defined at
this point.

# trace = 0
# t = z - 1
# a = 0
# while t%2 == 0:
# t = t/2
# a = a + 1
# test = pow(w,t,z)
# if test ==1:
# x = gcd(z,w-1)
# if x 1:
# if x < z:
# y = z/x
# print " Found factor by Strong probable prime
test,
>using withness ",w,"."
# return [x,y,0]
# else:
# x = gcd(test-1,z)
# if x 1:
# print " "
# print " In strongfac "
# print " Found1: x = ",x

You could do all of this with a single print:

print "\n In strongfac \nFound1: x = ", x

I won't go any further because its pointless given the discrepency
between
the data and the code, but hopefully those pointers will be helpful in
your
efforts to tidy the code into separate functions.

Alan G.

Tutor maillist - Tutor (AT) python (DOT) org

Alan Gauld wrote:

While others have made good suggestions to clarify the code I thought
I'd try to tackle the question of whether we had a bug in Python.

Unfortunately the debug output does not come from the code that's
posted so its difficult to figure out what's been happening.

For example, one apparently good and one "faulty" test:
>
>In strongfac
>Found1: x = 53799857
>Found1: y = 1858741
>face = [53799857L, 1858741L, 0]
>Found1: factor by strong probable prime test, using witnes
>15306543515214
>
Note the mis-spelling of witnes(sic) - it does not appear in the code!

Hmm Perhaps I caught that spelling error between the time I sent
the attached program file and the time I reran the program to demostrate
the error.


>Found1: factors are 53799857 1858741
>Found1: returning [53799857L, 1858741L, 0] to fermat routine.
>Retrieved from strongfac, face = [0, 0, 0]
>In fermat: k = 13 x = 0 y = 0 face = [0, 0, 0]
>
Similarly the first line has the text "factors are 53"

But in the code all instances of "factors are" are followed by the
word "by"

So I conclude the tests are not from this code. The fault may be in
this code
but I can't be sure

After I've followed the many good suggestions for making my program more
concise and readable,
I'll re-run it and see if I get the same difficulty at the same z's to
factor.

I will upload the source to my web page and create a path to it in my
index.html file.

However a couple of observations might help:
>
># def strongfac(z,w):
># x = gcd(z,w-1)
># if x 1:
># if x < z:
>
You can simpliffy this 2 stage test using either boolean operartors:

if x 1 and x < z:

R, almost uniquie to pyhon:

if 1 < x < z:

Hmmmmmm.

A good syntax to remember.

That removes one whole layer of indentation.
This trick can be applied in many places in the algorithm.
--
Also
>
>
># y = z/x
># print "Found factors by P-1 Method as part of Strong
>probable prime test, using witness",w,"."
># print " x = ",x," y = ",y
># 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:
># print "Found factors by square = square as
>part of
>Strong probable prime test, using witness",w,"."
># return [x,y,0]
>
If x was not between 1 and z in the first test y is not defined at
this point.

Yep. I should have calculated y = z/x before printing.

The syntax checker would have found this as soon as I encountered a z
that took me to that point.

I'll fix it before re-submitting.


># trace = 0
># t = z - 1
># a = 0
># while t%2 == 0:
># t = t/2
># a = a + 1
># test = pow(w,t,z)
># if test ==1:
># x = gcd(z,w-1)
># if x 1:
># if x < z:
># y = z/x
># print " Found factor by Strong probable prime test,
>using withness ",w,"."
># return [x,y,0]
># else:
># x = gcd(test-1,z)
># if x 1:
># print " "
># print " In strongfac "
># print " Found1: x = ",x
>
You could do all of this with a single print:

print "\n In strongfac \nFound1: x = ", x

uuuuuuuuuh Too compact for me.

I need to see the logic more spread out.

I won't go any further because its pointless given the discrepency
between
the data and the code, but hopefully those pointers will be helpful in
your
efforts to tidy the code into separate functions.

Alan G.

Also a warning to me to not edit the final output to compensate for
faulty programming.

Thank you.

Kermit < kermit (AT) polaris (DOT) net >

Tutor maillist - Tutor (AT) python (DOT) org

# print " "
# print " In strongfac "
# print " Found1: x = ",x
>>
>You could do all of this with a single print:
>>
>print "\n In strongfac \nFound1: x = ", x
>>
uuuuuuuuuh Too compact for me.
I need to see the logic more spread out.

\n is the newline character.
An alternative is to use triple quotes:

print '''
In strongfac
Found1: x = ''',x

But that still clutters up the code listing with extra lines that
have nothing to do with the algorithm - the main advantage in
reducing to one print statement

Alan G.

Tutor maillist - Tutor (AT) python (DOT) org

Alan Gauld wrote:
# print " "
# print " In strongfac "
# print " Found1: x = ",x

You could do all of this with a single print:

print "\n In strongfac \nFound1: x = ", x


>uuuuuuuuuh Too compact for me.
>I need to see the logic more spread out.
>
>
\n is the newline character.
An alternative is to use triple quotes:

print '''
In strongfac
Found1: x = ''',x

But that still clutters up the code listing with extra lines that
have nothing to do with the algorithm - the main advantage in
reducing to one print statement

This is obviously a matter of personal preference. I prefer the longer
form as well - I usually use a separate print statement for each line of
output. I would say it has everything to do with the function, if not
the algorithm - it clearly represents the form the output will take.

Kent

Tutor maillist - Tutor (AT) python (DOT) org

Alan Gauld wrote:

# print " "
# print " In strongfac "
# print " Found1: x = ",x

You could do all of this with a single print:

print "\n In strongfac \nFound1: x = ", x

>uuuuuuuuuh Too compact for me.
>I need to see the logic more spread out.
>
\n is the newline character.
--

Ah. Thanks. Explaining the backslash n helped me understand.

I will use the backslash n to reduce lines of print statements.

Kermit < kermit (AT) polaris (DOT) net >

Tutor maillist - Tutor (AT) python (DOT) org