473,325 Members | 2,860 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

processing limitation in Python

If I un-comment any line in this program below the line where I
commented " all OK up to this point " This program locks up my
computer.

Windows task manager will show "Not Responding" for Python in the
Applications tab and in the Performance tabe the CPU usage will be
locked at %100.

I've experienced the same problem on 2 different computers, one running
2000 pro. the other running XP home eddition. both computers run
Python 2.4.2

I'm just wondering if any one else has noticed any problems with
working with large numbers in Python ind if there is anything that can
work around this issue.

Thankd for reading
David

def factor(n):
d = 2
factors = [ ]
while n > 1:
if n % d == 0:
factors.append(d)
n = n/d
else:
d = d + 1
print factors
factor (12)
factor (123)
factor (1234)
factor (12345)
factor (123456)
factor (1234567)
factor (12345678)
factor (123456789)
factor (1234567898)
factor (12345678987)
factor (123456789876)
factor (1234567898765) # all OK up to this point
#factor (12345678987654) # locks up computer if I run this line
#factor (123456789876543)
#factor (1234567898765432)
#factor (12345678987654321)

Feb 14 '06 #1
7 1889
[pd***@comcast.net]
If I un-comment any line in this program below the line where I
commented " all OK up to this point " This program locks up my
computer.

Windows task manager will show "Not Responding" for Python in the
Applications tab and in the Performance tabe the CPU usage will be
locked at %100.

I've experienced the same problem on 2 different computers, one running
2000 pro. the other running XP home eddition. both computers run
Python 2.4.2

I'm just wondering if any one else has noticed any problems with
working with large numbers in Python ind if there is anything that can
work around this issue.

Thankd for reading
David

def factor(n):
d = 2
factors = [ ]
while n > 1:
if n % d == 0:
factors.append(d)
n = n/d
else:
d = d + 1
print factors
You primary problem is that this is a horridly inefficient way to
factor, taking time propotional to n's largest prime divisor (which
may be n).
factor (12)
factor (123)
factor (1234)
factor (12345)
factor (123456)
factor (1234567)
factor (12345678)
factor (123456789)
factor (1234567898)
factor (12345678987)
factor (123456789876)
factor (1234567898765) # all OK up to this point
#factor (12345678987654) # locks up computer if I run this line
It doesn't lock up for me, using Python 2.3.5 or 2.4.2 on Windows (XP
Pro SP2, but the specific flavor of Windows shouldn't matter). I ran
it from a DOS box, and while it was plugging away on 12345678987654,
hitting Ctrl+C stopped it.

If you let it continue running, and you & your computer were immortal
(something worth shooting for :-)), it would eventually print the
factorization. Since

12345678987654 = 2 * 3 * 2057613164609

the loop would have to go around over 2 trillion times to find the
final 2057613164609 prime factor. A simple enormous improvement is to
get out of the loop when d*d > n. Then n must be prime or 1. That
would slash the worst-care runtime from being proportional to n to
being proportional to sqrt(n).
...

Feb 14 '06 #2
Using CPython or GMPY with a smarter algorithm in acceptable time you
can find that:

12345678987654 == 2 * 3 * 2057613164609

It's a very big number to factorize with that naive algorithm, so the
program hangs... (I have used an online factoring service).

Bye,
bearophile

Feb 14 '06 #3
On 14 Feb 2006 08:42:38 -0800 in comp.lang.python, "pd***@comcast.net"
<pd***@comcast.net> wrote:
If I un-comment any line in this program below the line where I
commented " all OK up to this point " This program locks up my
computer.
Hmm. Ctrl-C gets me out just fine. In Idle, at least.

Windows task manager will show "Not Responding" for Python in the
Applications tab and in the Performance tabe the CPU usage will be
locked at %100.
Well sure. It's pretty busy code.

I've experienced the same problem on 2 different computers, one running
2000 pro. the other running XP home eddition. both computers run
Python 2.4.2

I'm just wondering if any one else has noticed any problems with
working with large numbers in Python ind if there is anything that can
work around this issue.


Try running with the changes I've made below, and see if that tells
you anything.

def factor(n):
d = 2
pctr = 0
factors = [ ]
while n > 1:
if n % d == 0:
factors.append(d)
n = n/d
else:
d = d + 1
pctr += 1
if pctr >= 1000000:
print "So Far: " + str(factors)
pctr = 0
print factors
factor (12)
factor (123)
factor (1234)
factor (12345)
factor (123456)
factor (1234567)
factor (12345678)
factor (123456789)
factor (1234567898)
factor (12345678987)
factor (123456789876)
factor (1234567898765) # all OK up to this point
factor (12345678987654) # locks up computer if I run this line
#factor (123456789876543)
#factor (1234567898765432)
#factor (12345678987654321)
Hint: 2057613164609L is a Really Big Number (tm). If it's prime (I
don't know if it is or not), it will take more than 46 days on my
computer to figure that out. Did you wait that long?

Regards,
-=Dave

--
Change is inevitable, progress is not.
Feb 14 '06 #4
On Tue, 14 Feb 2006 08:42:38 -0800, pd***@comcast.net wrote:
If I un-comment any line in this program below the line where I
commented " all OK up to this point " This program locks up my
computer.
It locks up the operating system as well? Shame on Windows.

What happens if you type ctrl-C to interrupt the processing?

I'm just wondering if any one else has noticed any problems with
working with large numbers in Python ind if there is anything that can
work around this issue.


Yes, you need a better algorithm.

You can prove to yourself that it isn't a problem with Python handling big
numbers by running this simple test:

factor(100000000000000000)

and watch how quickly it completes -- a fraction of a second. The problem
is that your test data have few factors, and so your function spends a
LONG time increasing d by one each iteration. Worst case, if your number
is a prime, it has to try to divide against *every* number, 2, 3, 4, ...
all the way up to the prime itself. This takes a LONG time if the number
is very large.

Some improvements you might like to try:

You have to check for factors of two. But after you have done that, you
are just wasting time to check for factors of 4, 6, 8, ... because they
can't possibly be factors. Pull the factor of two test out of the loop,
then start the test with d = 3 and increase by two instead of one.

You can stop looking for factors once you have reached the square root of
the original number. The square root is the biggest possible factor.

There are other improvements you can make, but they make the code more
complicated. Just these few things will give you a HUGE performance boost:

def factor(n):
factors = []
while n % 2 == 0:
factors.append(2)
n = n/2
d = 3
mx = int(n**0.5)
while (n > 1) and (d <= mx):
if n % d:
d = d+2
else:
factors.append(d)
n = n/d
if n != 1:
factors.append(n)
return factors
Using this new improved version, I get this calculation in about two
seconds:
factor(12345678987654) [2, 3, 2057613164609L]

and this in less than a second:
factor(12345678987654321)

[3, 3, 3, 3, 37, 37, 333667, 333667]

--
Steven.

Feb 14 '06 #5
Big help guys, thanks. There does seem to be a problem with Pythons
IDLE. If I run my oridgional program from a dos shell I can hit Ctrl-C
and free up the procesor, But running it in IDLE just locks up the
computer. Bad Windows. Thanks for the help with a more efficent
algorythm.

David KG2LI

Feb 15 '06 #6
pd***@comcast.net wrote:
But running it in IDLE just locks up the
computer. Bad Windows.


yeah, right - blame it all on Microsoft!

try ctrl-F6 (or Shell / Restart Shell from the menu) in IDLE, which
stops programs from infinite looping

- nas

Feb 15 '06 #7
On Wed, 15 Feb 2006 10:16:07 +0000, Dennis Lee Bieber wrote:
Why bother collecting the "factors" into a list only to print them
at the bottom of the procedure -- you aren't returning a value from
factor(), so I'd suggest dropping the
factors = []
and
print factors

replace
factors.append(d)
with
print d #optional , if you want as many on a line as possible
This is generally bad practice. You now have a function which can't
easily feed its output into any other function (without pipes, file
redirection and other tricks). The function is now locked down into one
rather limited use: printing the factors.

If you need the factors one at a time, the right way is to use a
generator, and yield them as they are found. Otherwise, the correct way to
solve this problem is to accumulate all the factors in a list and return
the list.

Among other things, besides not needing memory to store the entire
list, you also get to see it working as each one is found and printed.


The amount of memory needed to store the entire list is trivial for all
but the hugest numbers. A number with 1,000 factors would be enormous,
and yet the memory needed for a list of 1,000 ints could be as small as
8K -- trivial on modern computers.
--
Steven.

Feb 15 '06 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: christof hoeke | last post by:
hi, i wrote a small application which extracts a javadoc similar documentation for xslt stylesheets using python, xslt and pyana. using non-ascii characters was a problem. so i set the...
2
by: Claudio Grondi | last post by:
"You don't have to rely on expensive and proprietary EDI conversion software to parse, validate, and translate EDI X12 data to and from XML; you can build your own translator with any modern...
6
by: Newbie | last post by:
I am doing some robotics projects but my main area of interest is trying out several algorithms for the processing of the stream of data coming from the video. I am wondering what type of camera...
3
by: anthony hornby | last post by:
Hi, I am starting my honours degree project and part of it is going to be manipulating ASCII encoded XML files from a legacy database and converting them to Unicode and doing text processing stuff...
1
by: Erik Max Francis | last post by:
I've come across a limitation in unpickling certain types of complex data structures which involve instances that override __hash__, and was wondering if it was known (basic searches didn't seem to...
4
by: Alexis Gallagher | last post by:
(I tried to post this yesterday but I think my ISP ate it. Apologies if this is a double-post.) Is it possible to do very fast string processing in python? My bioinformatics application needs to...
4
by: ferrad | last post by:
I have not used Python before, but believe it may be what I need. I have large text files containing text, numbers, and junk. I want to delete large chunks process other bits, etc, much like I'd...
1
by: Xah Lee | last post by:
Text Processing with Emacs Lisp Xah Lee, 2007-10-29 This page gives a outline of how to use emacs lisp to do text processing, using a specific real-world problem as example. If you don't know...
0
by: Johannes Nix | last post by:
Hi, this might be of interest for people who are look for practical information on doing real-time signal processing, possibly using multiple CPUs, and wonder whether it's possible to use...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.