Almost-prime numbers; groups, rings and fields in mathematics

By Vasudev Ram

I saw this article on Scientific American about almost-primes today:

What Is an “Almost Prime” Number?

HN thread about it.

I commented, mentioning that groups, rings and fields of mathematics are cool, and underlie many other mathematical areas.

---

- Vasudev Ram - Online Python training and consulting

Hit the ground running with my vi quickstart tutorial, vetted by two Windows system administrator friends.

Jump to posts: Python * DLang * xtopdf

Interested in a Python, SQL or Linux course?

Get WP Engine, powerful managed WordPress hosting.

Subscribe to my blog (jugad2.blogspot.com) by email

My ActiveState Code recipes

---

Follow me on:

* Gumroad  * LinkedIn

  * Twitter

Do you create online products? Get Convertkit:

Email marketing for digital product creators

---

Porting a prime checker from Q to Python (with improvements)

By Vasudev Ram


Q => Py

Hi readers,

I was checking out the Q programming language.

It's an interesting language, a descendant of APL, that supports array and functional programming styles. Some information about Q from its Wikipedia page:

---

Paradigm: Array, functional
Designed by: Arthur Whitney
Developer: Kx Systems
First appeared: 2003
Typing discipline: Dynamic, strong
Influenced by: A+, APL, Scheme, K

---

Q is a proprietary array processing language developed by Arthur Whitney and commercialized by Kx Systems. The language serves as the query language for kdb+, a disk based and in-memory, column-based database. kdb+ is based upon K, a terse variant of APL. Q is a thin wrapper around K, providing a more readable, English-like interface.

---

I had tried out Q a bit recently, using one of the tutorials.

Then, while reading the Q Wikipedia page again, I saw this paragraph:

[
When x is an integer greater than 2, the following function will return 1 if it is a prime, otherwise 0:

{min x mod 2_til x}
The function is evaluated from right to left:

"til x" enumerate the positive integers less than x.
"2_" drops the first two elements of the enumeration (0 and 1).
"x mod" performs modulo division between the original integer and each value in the truncated list.
"min" find the minimum value of the list of modulo result.
]

It's basically an algorithm in Q to find whether a given number x (> 2) is prime or not [1]. The algorithm returns 1 if x is a prime, else 0. Notice how concise it is. That conciseness is a property of the APL family of languages, such as APL, J and Q. In fact Q is slightly less concise than some of the others, I've read, because it puts a thin English-like wrapper on the hard-core APL symbolic syntax. But all of them are still very concise.

So I thought of implementing that algorithm in Python, just for fun. I first wrote a naive version, more or less a port of the Q version. Then I rewrote that first version in a more functional way. Then I realized that there are other opportunities for improving the code [2], and implemented a few of them.

So I combined the few different versions of the is_prime_* functions (where * = 1, 2, 3, etc.) that I had written, in a single program, with a driver function to exercise all of them. The code is in file is_prime.py, shown further below. There are comments in the program that explain the logic and improvements or differences of the various is_prime function versions.

[1] Prime_number

[2] There are obviously many other ways of checking if numbers are prime, and many of them are faster than these approaches; see [3]. These are not among the most efficient ways, or even close; I was just experimenting with different ways of rewriting and refactoring the code, after the initial port from Q to Python. Even the original Q version in the Wikipedia page was not meant to be a fast version, since it does not use any of the improvements I mention below, let alone using any special Q-specific algorithm or language feature, or advanced general prime-finding algorithms.

[3] Primality test

There might still be some scope for further changes or improvements, some of which I may do in a future post. A few such improvements are:

1. Don't divide x by all values up to x - 1. Instead, only check up to the square root of x. This is a standard improvement often taught to programming beginners; in fact, it is mentioned in the Wikipedia articles about primes.

2. Terminate early when the first remainder equal to 0 is found. This avoids unnecessarily computing all the other remainders. I did that in is_prime_3().

3. Don't check for divisibility by any even number > 2 (call it b), because if any such b divides x evenly, then so will 2, and we would have checked earlier if 2 divides x evenly.

4. Create a function for the output statements, most of which are common across the different is_prime versions, and call that function instead from those places.

5. Use a generator to lazily yield divisors, and when any divisor gives a zero remainder, exit early, since it means the number is not prime. Done in is_prime_4().

Other ways of doing it may include use of some other functional programming features of Python such as filter(), itertools.takewhile/dropwhile, etc. (The itertools module has many functions and is very interesting, but that is a subject for a different post.)

I also observed some interesting behavior when running the program with large ranges of inputs for prime number checking. Will analyze that a bit and write about my opinions on that in a future post.

Here is the code for is_prime.py:

# File: isprime.py
# A port of a primality checking algorithm from the Q language to Python, 
# plus a few improvements / variations, using Python features.
# Ref: https://en.wikipedia.org/wiki/Q_(programming_language_from_Kx_Systems)
# Search for the word "prime" in that page to see the Q code.

# Author: Vasudev Ram
# Copyright 2018 Vasudev Ram
# Web site: https://vasudevram.github.io
# Blog: https://jugad2.blogspot.com
# Product store: https://gumroad.com/vasudevram

from __future__ import print_function
from debug1 import debug1

import sys

# Naive, mostly procedural port from the Q version.
def is_prime_1(x):
    # Guard against invalid argument.
    assert x > 2, "in is_prime_1: x > 2 failed"
    # The range of integers from 0 to x - 1
    til_x = range(x)
    # The range without the first 2 items, 0 and 1.
    divs = til_x[2:]
    # The remainders after dividing x by each integer in divs.
    mods = map(lambda d: x % d, divs)
    # x is prime if the minimum-valued remainder equals 1.
    return min(mods) == 1

# Shorter, more functional version, with nested calls 
# to min, map and range.
def is_prime_2(x):
    assert x > 2, "in is_prime_2: x > 2 failed"
    # Eliminate slicing used in is_prime_1, just do range(2, x).
    return min(map(lambda d: x % d, range(2, x))) == 1

# Early-terminating version, when 1st remainder equal to 0 found, 
# using a list for the range of divisors.
def is_prime_3(x):
    assert x > 2, "in is_prime_3: x > 2 failed"
    divs = range(2, x)
    # Check if x is divisible by any integer in divs; if so, 
    # x is not prime, so terminate early.
    debug1("in is_prime_3, x", x)
    for div in divs:
        debug1("  in loop, div", div)
        if x % div == 0:
            return False
    # If we reach here, x was not divisible by any integer in 
    # 2 to x - 1, so x is prime.
    return True

# Generator function to yield the divisors one at a time, to 
# avoid creating the whole list of divisors up front.
def gen_range(start, x):
    assert start > 0, "in gen_range, start > 0 failed"
    assert x > start, "in gen_range, x > start failed"
    i = start
    while i < x:
        yield i
        i += 1

# Early-terminating version, when 1st remainder equal to 0 found, 
# using a generator for the range of divisors.
def is_prime_4(x):
    assert x > 2, "in is_prime_4, x > 2 failed"
    divs = gen_range(2, x)
    debug1("in is_prime_4, x", x)
    for div in divs:
        debug1("  in loop, div", div)
        if x % div == 0:
            return False
    return True

def check_primes(low, high):
    assert low <= high, "in check_primes, low <= high failed"

    """
    print("\nWith a for loop:")
    for x in range(low, high + 1):
        print(x, "is" if is_prime_1(x) else "is not", "prime,", end=" ")
    print()
    """

    print("\nWith nested function calls:")
    output = [ str(x) + (" prime" if is_prime_2(x) else " not prime") \
        for x in range(low, high + 1) ]
    print(", ".join(output))

    print("\nWith a list of divisors and early termination:")
    output = [ str(x) + (" prime" if is_prime_3(x) else " not prime") \
        for x in range(low, high + 1) ]
    print(", ".join(output))

    print("\nWith a generator of divisors and early termination:")
    output = [ str(x) + (" prime" if is_prime_4(x) else " not prime") \
        for x in range(low, high + 1) ]
    print(", ".join(output))

def main():
    try:
        low = int(sys.argv[1])
        high = int(sys.argv[2])
        if low <= 2:
            print("Error: Low value must be > 2.")
            sys.exit(1)
        if high < low:
            print("Error: High value must be >= low value.")
            sys.exit(1)
        print("Checking primality of integers between {} and {}".format(low, high))
        check_primes(low, high)
        sys.exit(0)
    except ValueError as ve:
        print("Caught ValueError: {}".format(str(ve)))
    except IndexError as ie:
        print("Caught IndexError: {}".format(str(ie)))
    sys.exit(1)

if __name__ == '__main__':
    main()

And here are some runs of the output, below, both for normal and error cases. Note that I used my debug1() debugging utility function in a few places, to show what divisors are being used, in a few places. This helps show that the early termination logic works. To turn off debugging output, simply use the -O option, like this example:

python -O is_prime.py other_args

This improved version of the debug1 function (get it here), unlike the earlier version that was shown in this blog post:

A simple Python debugging function

, does not require the user to set any environment variables like VR_DEBUG, since it uses Python's built-in __debug__ variable instead. So to enable debugging, nothing extra needs to be done, since that variable is set to True by default. To disable debugging, all we have to do is pass the -O option on the python command line.

Here is the prime program's output:

Try this one later (if you're trying out the program), since it takes 
longer to run. You may observe some interesting behavior:

$ python -O is_prime.py 3 10000 | less

where less is the Unix 'less' command, a text pager. Any command-line text pager 
that can read standard input (from a pipe) will work.

Try some of these below (both normal and error cases) before the one above:

Some error-handling cases:

$ python -O is_prime.py 0 0
Error: Low value must be > 2.

$ python -O is_prime.py 2 0
Error: Low value must be > 2.

$ python -O is_prime.py 3 0
Error: High value must be >= low value.

$ python -O is_prime.py 4 2
Error: High value must be >= low value.

Some normal cases:

$ python -O is_prime.py 3 3
Checking primality of integers between 3 and 3

With nested function calls:
3 prime

With a list of divisors and early termination:
3 prime

With a generator of divisors and early termination:
3 prime

To show that the early termination logic works, run the program without 
the -O option. 
Here is one such run. Due to more debugging output, I've only checked 
two numbers, 4 and 5. But you can try with any number of values if you 
page the output, or redirect it to a file.

$ python is_prime.py 4 5
Checking primality of integers between 4 and 5

With nested function calls:
4 not prime, 5 prime

With a list of divisors and early termination:
in is_prime_3, x: 4
  in loop, div: 2
in is_prime_3, x: 5
  in loop, div: 2
  in loop, div: 3
  in loop, div: 4
4 not prime, 5 prime

With a generator of divisors and early termination:
in is_prime_4, x: 4
  in loop, div: 2
in is_prime_4, x: 5
  in loop, div: 2
  in loop, div: 3
  in loop, div: 4
4 not prime, 5 prime

You can see from the above run that for 4, the checking stops early, 
at the first divisor (2), in fact, because it evenly divides 4.
But for 5, all divisors from 2 to 4 are checked, because 5 has 
no prime factors (except itself and 1).

And here is a run checking for primes between 3 and 30:

$ python -O is_prime.py 3 30
Checking primality of integers between 3 and 30

With nested function calls:
3 prime, 4 not prime, 5 prime, 6 not prime, 7 prime, 8 not prime, 9 not prime, 
10 not prime, 11 prime, 12 not prime, 13 prime, 14 not prime, 15 not prime, 
16 not prime, 17 prime, 18 not prime, 19 prime, 20 not prime, 21 not prime, 
22 not prime, 23 prime, 24 not prime, 25 not prime, 26 not prime, 27 not prime, 
28 not prime, 29 prime, 30 not prime

With a list of divisors and early termination:
3 prime, 4 not prime, 5 prime, 6 not prime, 7 prime, 8 not prime, 9 not prime, 
10 not prime, 11 prime, 12 not prime, 13 prime, 14 not prime, 15 not prime, 
16 not prime, 17 prime, 18 not prime, 19 prime, 20 not prime, 21 not prime, 
22 not prime, 23 prime, 24 not prime, 25 not prime, 26 not prime, 27 not prime, 
28 not prime, 29 prime, 30 not prime

With a generator of divisors and early termination:
3 prime, 4 not prime, 5 prime, 6 not prime, 7 prime, 8 not prime, 9 not prime, 
10 not prime, 11 prime, 12 not prime, 13 prime, 14 not prime, 15 not prime, 
16 not prime, 17 prime, 18 not prime, 19 prime, 20 not prime, 21 not prime, 
22 not prime, 23 prime, 24 not prime, 25 not prime, 26 not prime, 27 not prime, 
28 not prime, 29 prime, 30 not prime

You can see that all three functions (is_prime_2 to 4) give the same results. 
(I commented out the call to the naive function version, is_prime_1, after 
a few runs (not shown), so none of these outputs shows its results, but they 
are the same as the others, except for minor formatting differences, due to 
the slightly different output statements used.

I also timed the program for finding primes up to 1000 and 10,000 
(using my own simple command timing program written in Python - not shown).

Command: python -O is_prime.py 3 1000
Time taken: 2.79 seconds
Return code: 0

Command: python -O is_prime.py 3 10000
Time taken: 66.28 seconds
Return code: 0

Related links:

Q (programming_language from Kx_Systems

Kx Systems

Kdb+

Column-oriented DBMS

In-memory database

If you want to try out Q, Kx Systems a free version available for download for non-commercial use, here: Q downloads

Enjoy.

- Vasudev Ram - Online Python training and consulting

Get fast web hosting with A2Hosting.com

Get updates (via Gumroad) on my forthcoming apps and content.

Jump to posts: Python * DLang * xtopdf

Subscribe to my blog by email

My ActiveState Code recipes

Follow me on: LinkedIn * Twitter

Are you a blogger with some traffic? Get Convertkit:

Email marketing for professional bloggers

Share |

Permutation facts

By Vasudev Ram

Nicomachus theorem 3D image attribution

Today, I was using the permutations function in Python's itertools module to generate permutations for a few different values of integers, as part of some work I was doing. Looking at the lengths (1, 2, 6, 24, ...) of a few sets of permutations, I noticed a pattern that seemed familiar, so I wrote this program to verify my guess about what it meant:

#--------------------------------------------------------------
# perm_fact.py
# Author: Vasudev Ram
# Copyright 2016 Vasudev Ram
# Web site: https://vasudevram.github.io
# Blog: http://jugad2.blotspot.com
# Product store: https://gumroad.com/vasudevram
#--------------------------------------------------------------

import sys
from itertools import permutations

def num_perms_upto(n):
    num_perms = []
    for i in range(1, n + 1):
        num_perms.append(len(list(permutations(range(i)))))
    return num_perms

def factorial(n):
    if n < 0:
        print "Argument n should be >= 0"
        sys.exit(0)
    if n == 0:
        return 1
    return n * factorial(n - 1)

def factorials_upto(n):
    factorials = []
    for i in range(1, n + 1):
        factorials.append(factorial(i))
    return factorials

print "Number of permutations of 1 .. n, where n in 1 .. 10:"
print num_perms_upto(10)
print "Factorial of n, where n in 1 .. 10:"
print factorials_upto(10)

which, when run, gave this output:

$ python perm_fact.py
Number of permutations of 1 .. n, where n in 1 .. 10:
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
Factorial of n, where n in 1 .. 10:
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

This confirmed (empirically, of course) that the number of permutations of n items (taken n at a time), is just n factorial.

Then I looked up factorial in Wikipedia, and found some interesting facts (pun intended). Here are some excerpts from that page:

[
The factorial operation is encountered in many areas of mathematics, notably in combinatorics, algebra, and mathematical analysis.
...
Its most basic occurrence is the fact that there are n! ways to arrange n distinct objects into a sequence (i.e., permutations of the set of objects). This fact was known at least as early as the 12th century, to Indian scholars. Fabian Stedman, in 1677, described factorials as applied to change ringing.
...
Although the factorial function has its roots in combinatorics, formulas involving factorials occur in many areas of mathematics.
...
Factorials occur in algebra for various reasons, such as via the already mentioned coefficients of the binomial formula.
...
Factorials also turn up in calculus; for example they occur in the denominators of the terms of Taylor's formula.
...
Factorials are also used extensively in probability theory.
...
As n grows, the factorial n! increases faster than all polynomials and exponential functions (but slower than double exponential functions) in n.
...
(Hence) ln n! ~ n ln n ... This result plays a key role in the analysis of the computational complexity of sorting algorithms
...
Factorials have many applications in number theory.
...
The reciprocals of factorials produce a convergent series whose sum is Euler's number e:
...
In mathematics, the gamma function (represented by the capital Greek letter G) is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers.
...
The gamma function is applicable in the fields of probability and statistics, as well as combinatorics.
...
There are several other integer sequences similar to the factorial that are used in mathematics:
...
Double factorial
...
Quadruple factorial
...
Superfactorial
...
Hyperfactorial
...
Bhargava factorial
]

I did a double take (or should that be factorial take? :) when I saw that one, because I didn't expect a factorial type to be named after a person (but why not, really); the person is Fields Medal-winning mathematician Manjul Bhargava.

All the above factorial-related terms are mentioned in the Wikipedia factorial article, and there are also links to some of them there.

And did you know that triangular numbers are the additive analogues of factorials?

The image at the top of the post is a visual representation of Nicomachus's theorem, which involves what are called squared triangular numbers. His theorem says that:

The sum of the first n cubes is the square of the nth triangular number. That is,

1 cubed + 2 cubed + 3 cubed + ... + n cubed = (1 + 2 + 3 + ... + n) squared,

where the nth triangular number is the sum of the natural numbers from 1 to n.

Speaking of mathematics, you may also like this earlier post by me:

Bhaskaracharya and the man who found zero. In fact, the Wikipedia article on permutations says that the relationship between permutations and factorials (described above) was known to mathematicians in India by around 1150 A.D.

- Enjoy.

- Vasudev Ram - Online Python training and consulting

Get updates on my software products / ebooks / courses.

Jump to posts: Python   DLang   xtopdf

Subscribe to my blog by email

My ActiveState recipes

FlyWheel - Managed WordPress Hosting

Share |

The many uses of randomness - Part 2

By Vasudev Ram

Denarius image attribution

Hi, readers,

In my previous (and first) post on randomness, titled:

The many uses of randomness ,

I had described some uses of random numbers related to floats, and ended by saying I would continue in the next post, with other uses, such as for strings (and things).

This is that next post (delayed some, sorry about that).

Assume that the following statements have been executed first in your Python program or in your Python shell:

from __future__ import print_function
import string
from random import random, randint, randrange, choice, shuffle

Let's look now at the use of random numbers to generate random character and string data.

First, let's generate a few different kinds of random characters:

1) Random characters from the range of 7-bit ASCII characters, i.e. the characters with ASCII codes 0 to 127. This expression generates a single ASCII character:

chr(randint(0, 127))

Each time the above expression is evaluated, it will generate a random character whose code is between 0 and 127.

As a result, it may sometimes generate non-printable characters, such as the characters with codes in the range 0 to 31, and 127. See the Wikipedia article about ASCII above, for information on printable versus non-printable characters.

To generate only printable ASCII characters, use:

choice(string.printable)

We may want to generate all ASCII characters, or even all printable characters, only for some specialized purposes. More commonly, we may want to generate printable random characters from a specific subset of the complete ASCII character set. Some examples of this would be: generating random uppercase letters, random lowercase letters, random numeric digits, or combinations of those. Here are a few code snippets for those cases:

# Generate random uppercase letter.
chr(randint(ord('A'), ord('Z')))

(which relies on the fact that the ASCII codes for the characters 'A' through 'Z' are contiguous).
Or, another way:

# Generate random uppercase letter.
choice(string.ascii_uppercase)
# -------------------------------------------

# Generate random lowercase letter.
chr(randint(ord('a'), ord('z')))

Or, another way:

# Generate random lowercase letter.
choice(string.ascii_lowercase)

Random numbers can be used to generate random strings, where the randomness of the strings can be in either or both of two dimensions, the content or the length:

Generate strings with random character content but fixed length, e.g.: "tdczs", "ohybi", "qhmyf", "elazk"

def rand_lcase_str(n):
    '''Return string of n random lowercase letters.'''
    assert n > 0
    rand_chars = [ choice(string.ascii_lowercase) for i in range(n) ]
    return ''.join(rand_chars)

# Calls and output:
[ rand_lcase_str(3) for i in range(1, 8) ]
['xio', 'qsc', 'omt', 'fnn', 'ezz', 'get', 'frs']
[ rand_lcase_str(7) for i in range(1, 4) ]
['hazrdwu', 'sfvvxno', 'djmhxri']

Generate strings with fixed character content but random lengths, e.g.: "g", "gggg", "gg", "ggggg", "ggg"; all strings contain only letter g's, but are of different lengths.

def rand_len_fixed_char_str(c, low_len=1, high_len=256):
    '''Return a string containing a number of characters c,
    varying randomly in length between low_len and high_len'''
    assert len(c) == 1
    assert 0 < low_len <= high_len
    rand_chars = c * randint(low_len, high_len)
    return rand_chars

# Calls and output:
[ rand_len_fixed_char_str('g', 3, 8) for i in range(10) ]
['gggg',
 'ggggggg',
 'ggg',
 'ggggggg',
 'ggggg',
 'ggggg',
 'gggggg',
 'gggggg',
 'gggggg',
 'ggggg']

Generate strings with both random character content and random lengths, e.g.: "phze", "ysqhdty", "mltstwdg", "bnr", "q", "ifgcvgrey". This should be easy after the above snippets, since we can use parts of the logic from some of them, so is left as an exercise for the reader.

Such kinds of randomly generated data are useful for many purposes, e.g. for testing apps that read or write CSV or TSV files, fixed-length or variable-length records, spreadsheets, databases; for testing report generation logic (particularly with respect to text formatting, wrapping, centering, justification, logic related to column and line widths, etc.).

All these use cases can benefit from running them on random data (maybe with some programmed constraints, as I showed above), to more thoroughly test the app than can be done manually by typing in, say, only a few dozen variations of test data. There are at least two benefits here:

- a program can be more systematically random (if that makes sense) than a human can, thereby giving test data that provides better coverage;

- the computer can generate large volumes of random data for testing the app, much faster than a human can. It can also feed it as input to the software you want to test, faster than a human can, e.g. by reading it from a file instead of a user typing it. So overall, (parts of) your testing work can get done a lot faster.

In the next part, I'll show how, using a mathematical concept, random numbers can be used to reduce the amount of test data needed to test some apps, while still maintaining a good level of quality of testing. I will also discuss / show some other uses of randomness, such as in web development, and simulating physical events.

The image at the top of the post is of a Roman denarius in silver of Maximinus (235-238). The word denarius seems to be the origin of the word for money in multiple modern languages, according to the linked article.

- Vasudev Ram - Online Python training and consulting

Signup to hear about my new courses and products.

My Python posts     Subscribe to my blog by email

My ActiveState recipes

Share |

Swapping two variables without using a third, 1) generically and 2) Pythonically

By Vasudev Ram

One of the techniques taught in some beginners' programming courses, is how to swap the values of two variables, without using a third variable. It is sometimes given as an exercise to students. I remember it from an early course that I took.

[ If you don't know the solution, try it before reading on. Hint: Try it for two integers. No restrictions, other than not being allowed to use a third variable. ]
.
.
.
.
.
One solution to it, at least when the two variables contain integer values, is like this:

>>> a, b = 1, 2
>>> print a, b
1 2
>>> a = a + b
>>> a, b
(3, 2)
>>> b = a - b
>>> a, b
(3, 1)
>>> a = a - b
>>> print a, b
2 1

Of course, the above method will only work for numbers, i.e. at least, for integers; it might or not work for all pairs a and b when a and b are floating-point numbers. Why? (*)

Similarly, it will not work when a and b are strings or any other data type.

(*) One reason it may not work for all floats (only some - I need to check this), is because some float values cannot be represented exactly in a computer that uses binary representation of numbers.

So that was the generic way, above (to swap the values of two integer variables, without using a third temporary variable), which will work in most or all programming languages.

Python has another, Pythonic way (though it also works in some other languages, I guess). It's just:

a, b = b, a

which does a parallel assignment of a and b's old values to each other, without overwriting either.

Interestingly, this 2nd way, since it does not involve addition and subtraction (as in a + b and a - b), is more general. For example, we can swap the values of two function objects:

>>> def foo(): print "this is function foo"
...
>>> def bar(): print "this is function bar"
...
>>> foo()
this is function foo
>>>
>>> bar()
this is function bar
>>>
>>> foo
<function foo at 0x00000000029F09E8>
>>> bar
<function bar at 0x00000000029F0518>
>>>
>>> foo, bar = bar, foo
>>>
>>> foo()
this is function bar
>>> bar()
this is function foo
>>> foo
<function bar at 0x00000000029F0518>
>>> bar
<function foo at 0x00000000029F09E8>

Note that both calling the function, like foo(), and just entering its name at the Python shell, like foo, tell us that the name foo now refers to the original bar function object. And similarly the name bar now refers to the original foo function object.

And finally, to show what happens in the above function object swap, in a different way:

>>> id(foo), id(bar)
(43977192L, 43975960L)
>>> foo, bar = bar, foo
>>>
>>> id(foo), id(bar)
(43975960L, 43977192L)

After writing this post, I googled for "swapping two variables without using temp" and found an interesting hit:

Swap Two Variables Without Using a Temp Variable (With Math!)

which throws more light on this subject, showing other ways to do it, and also goes into the mathematical theory behind it (involving groups - the mathematical kind) - which I remember as a fun math topic from college, with many applications in the real world. I even got to know about quasigroups from that post ... whew!

Referring to the swapping of function objects above, coincidentally, just recently I came across a post by Ned Batchelder on a very related topic: names and values in Python. The exact meaning of (identifier) names and values in Python is not as obvious as it may seem at first, and is also somewhat different from the way these things work in other languages like C or Java. It has to do with concepts like binding names to values (and also unbinding and rebinding them). Here is his post, which he also presented as a video at PyCon 2015:

Python Names and Values

There is a link to the video in his post, and it is also embedded below:

- Vasudev Ram - Online Python training and programming

Dancing Bison Enterprises

Signup to hear about new products and services I create.

Posts about Python  Posts about xtopdf

Contact Page

Share |

Converting numeric strings to integers with handrolled code

By Vasudev Ram

-

A while ago, I was explaining to someone, how different data types such as numbers and strings are represented in a computer. That made me think of writing a simple program, called str_to_int.py, similar to Python's built-in int() function, to show them roughly what steps are involved in the process of converting a numeric string, such as '123', to an integer.

There are many different solutions possible for this task, and some may be more efficient or simpler than others, of course. This was just my first quick attempt at it (in Python, because I had no need to do it earlier, though I've done it before in assembly language and in C; in C it would be like the atoi() function in the C standard library). Note that this program does not handle all the cases that Python's int() does. It's just meant to show the basics of the process.

Here is the source code for str_to_int.py:

def str_to_int(s):
    ctr = i = 0
    for c in reversed(s):
        i += (ord(c) - 48) * (10 ** ctr)
        ctr += 1
    return i

print
for s in ('0', '1', '2', '3', '12', '123', '234', '456', '567'):
    i = str_to_int(s)
    print "s = {}, i = {} |".format(s, i),

print
print

for i in range(50):
    s = str(i)
    j = str_to_int(s)
    print "s = {}, j = {} |".format(s, j), 

And here is its output:

$ py str_to_int.py

s = 0, i = 0 | s = 1, i = 1 | s = 2, i = 2 | s = 3, i = 3 | s = 12, i = 12 | s =
 123, i = 123 | s = 234, i = 234 | s = 456, i = 456 | s = 567, i = 567 |

s = 0, j = 0 | s = 1, j = 1 | s = 2, j = 2 | s = 3, j = 3 | s = 4, j = 4 | s = 5
, j = 5 | s = 6, j = 6 | s = 7, j = 7 | s = 8, j = 8 | s = 9, j = 9 | s = 10, j
= 10 | s = 11, j = 11 | s = 12, j = 12 | s = 13, j = 13 | s = 14, j = 14 | s = 1
5, j = 15 | s = 16, j = 16 | s = 17, j = 17 | s = 18, j = 18 | s = 19, j = 19 |
s = 20, j = 20 | s = 21, j = 21 | s = 22, j = 22 | s = 23, j = 23 | s = 24, j =
24 | s = 25, j = 25 | s = 26, j = 26 | s = 27, j = 27 | s = 28, j = 28 | s = 29,
 j = 29 | s = 30, j = 30 | s = 31, j = 31 | s = 32, j = 32 | s = 33, j = 33 | s
= 34, j = 34 | s = 35, j = 35 | s = 36, j = 36 | s = 37, j = 37 | s = 38, j = 38
 | s = 39, j = 39 | s = 40, j = 40 | s = 41, j = 41 | s = 42, j = 42 | s = 43, j
 = 43 | s = 44, j = 44 | s = 45, j = 45 | s = 46, j = 46 | s = 47, j = 47 | s =
48, j = 48 | s = 49, j = 49 |

To get the documentation for int(), you can do this:

>>> print int.__doc__

which gives this as the output:

int(x=0) -> int or long
int(x, base=10) -> int or long

Convert a number or string to an integer, or return 0 if no arguments
are given.  If x is floating point, the conversion truncates towards zero.
If x is outside the integer range, the function returns a long instead.

If x is not a number or if base is given, then x must be a string or
Unicode object representing an integer literal in the given base.  The
literal can be preceded by '+' or '-' and be surrounded by whitespace.
The base defaults to 10.  Valid bases are 0 and 2-36.  Base 0 means to
interpret the base from the string as an integer literal.
>>> int('0b100', base=0)
4

Learn more about this overall topic at the Wikipedia article on numeral systems.
Also check out my earlier post about Bhaskaracharya and the man who found zero.

Kthxbye :)

Vasudev Ram - Online Python training and programming

Dancing Bison Enterprises

Signup to hear about new Python products or services that I create.

Posts about Python  Posts about xtopdf

Contact Page

Share |

pygal, a Python SVG charting library

By Vasudev Ram

I came across pygal recently. It is a Kozea project. They also have some other interesting projects, some of which are in Python. lxml is the only needed dependency for pygal.

I tried out a simple example from the pygal site, which generates a graph of Fibonacci numbers, and then enhanced it a bit to add a graph of a univariate quadratic function, which represents a parabola, in the same plot. The quadratic function I used was:

3x^2 + 2x + 4 (three x squared plus two x plus four)

[ Also check out:

Quadratic equations

and

the quadratic formula

if not known (or not remembered from high school mathematics :)

And speaking of quadratics (functions, formulae, equations and so on), also check out my earlier post:

Bhaskaracharya and the man who found zero, which briefly mentioned Brahmagupta, an ancient Indian mathematician, who is supposed to be the discoverer of the number zero, without which practically no modern science or technology (including computers and software :) would be possible. He also gave "the first explicit (although still not completely general) solution of the quadratic equation ax^2 + bx = c", according to the Wikipedia article about him, linked to in the previous sentence.

]

Here is the modified pygal example program, in test_pygal.py:

import pygal

bar_chart = pygal.Bar()
bar_chart.add('Fibonacci', [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55])
bar_chart.render_to_file('bar_chart.svg')

def quadratic(a, b, c, x):
    return a * x * x + b * x + c

bar_chart.add('Quadratic', [quadratic(3, 2, 4, x) for x in range(1, 10)])
bar_chart.render_to_file('bar_chart.svg')

I ran it with:

py test_pygal.py

[ Learn more about py here: py, the Python Launcher for Windows ]

And here is a screenshot of the output of running the test pygal program:

You can intuitively see that if you drew a curve joining the tops of the green bars in the screenshot, it would approximate a parabola. Parabolas occur a lot in nature too, as do many other mathematical concepts or principles.

- Enjoy.

- Vasudev Ram - Online Python training and programming

Dancing Bison Enterprises

Signup to hear about new products or services that I create.

Posts about Python  Posts about xtopdf

Contact Page

Share |

The SageMath Cloud - Python and computational mathematics in the cloud

By Vasudev Ram

I got to know about this today, via this post:

Hello Planet Python (seen via Planet Python).

The SageMath Cloud (beta) is a new development by William Stein, a professor of mathematics at the University of Washington, who started the SageMath project.

I had blogged about Sage earlier, here:

Calculize and Sage Notebook, online math tools

So today I signed up for a free account on the SageMath Cloud and then tried to enter and run a simple Python factorial program. After a hitch or two (it's beta), it worked.

Here is a screenshot of the factorial program in SageMath Cloud (click image to enlarge):

And here's a screenshot of the result of running "python factorial.py" in the command-line box of SageMath Cloud (click image to enlarge):

Here's a post that I found, by the creator of SageMath Cloud, William Stein himself, talking about his work on it. He mentions using ZFS and plans to use Google Compute Engine for the SageMath Cloud:

Holiday Coding the SageMath Cloud


- Vasudev Ram - Dancing Bison Enterprises

Contact Page

Share |

Calculize and Sage Notebook, online math tools

By Vasudev Ram - dancingbison.com | @vasudevram | jugad2.blogspot.com

Calculize and Sage Notebook are two tools for doing mathematics online , i.e. in the browser.
Calculize seems to use its own language for writing math expressions. Sage Notebook supports some widely used math-specific languages, as well as the programming languages R and Python. On a related note, I had blogged earlier about Resolver Systems' PythonAnywhere product, which also lets you run Python in the browser, in this post.
Calculize was mentioned in a post on Hacker News recently. Sage Notebook was mentioned in the comments.

Calculize is at calculize.com

I registered for it (free) and then tried running a simple example. Screenshot below.



Did the same for Sage Notebook (again, registration is free), except that in this case I used the Python mode and defined a few simple Python expressions and then evaluated them, in the browser.

About Sage Notebook: http://nb.sagemath.org/

Sage Notebook is at sagenb.com

Screenshot of my Sage Notebook trial below:



By Vasudev Ram @ Dancing Bison

Share
|