473,573 Members | 2,504 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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 (12345678987654 3)
#factor (12345678987654 32)
#factor (12345678987654 321)

Feb 14 '06 #1
7 1896
[pd***@comcast.n et]
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.pytho n, "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 (12345678987654 3)
#factor (12345678987654 32)
#factor (12345678987654 321)
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.n et 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(10000000 0000000000)

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(12345678 987654) [2, 3, 2057613164609L]

and this in less than a second:
factor(12345678 987654321)

[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.n et 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
2543
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 defaultending to UTF-8 and now everything works (at least it seems so, need to do more testing though). it may not be the most elegant solution (according...
2
2428
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 programming language, such as Python." by Jeremy Jones http://www.devx.com/enterprise/Article/26854 Excerpt: "Python is an object-oriented,...
6
3399
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 I should invest in. Either I could buy a web cam and hope I can find a driver I could either modify or use. i.e. every frame is somehow stored on...
3
1374
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 on the data. I am new to python ( total n00b ) but am keen to use it as the rest of the software my application has to extend is already written...
1
2266
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 come up with anything similar) and if there is a workaround for it short of restructuring the data structures in question. The fundamental issue...
4
3590
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 scan very large ASCII files (80GB+), compare adjacent lines, and conditionally do some further processing. I believe the disk i/o is the main...
4
1513
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 do in an editor, but want to do it automatically. I have a set of generic rules that my fingers follow to process these files, which all follow a...
1
3424
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 elisp, first take a gander at Emacs Lisp Basics. HTML version with links and colors is at: http://xahlee.org/emacs/elisp_text_processing.html
0
1600
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 Python for audio-type worst case latencies (around 25 ms). I've done that in my PhD work, both with real-time requirements on dual-CPU
0
7746
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7983
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
8179
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
0
6356
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
0
5257
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3698
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
2166
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1269
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
992
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

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.