Creating a Program to Decompose a Number and Run a Function on that Decomposition

C

CTSB01

I've been puzzling over how to get a certain function working in Python. The function, takes positive integers to other positive integers as follows:

Phi_m(n2) = Phi_m(m*n + r) = m*x[n1] + r*(x[n1 + 1] - x[n1])

The above terms are all integer valued and are defined as follows:

n2 = the (n2)th slot of the output string

m = a fixed positive integer

n = some multiple of m such that n*m is less than or equal to n2

r = a remainder term to fill in the amount missing from n*m in decomposing n2

x[n1] = the element in the [n1]th slot of the input string

x[n1 + 1] = the element in the [n1 + 1]th slot of the input string

In general we start with a string of numbers, say 0, 1, 1, 2, 3, 3 and end up with a string of (k+1)m-1 terms, where k is the number of terms you started with. To use the function we first fix an m, say m = 2. Now we decompose n2 in terms of m, where n2 is representing a 'slot' of our output sequence. Say n2=5. Then we are asking 'what is in the fifth 'slot' of our output string'. In this case our total output string will be of length (5+1)2+1. Notice that we do not count 0 - it is always present and is for our purposes the 0th term, hence we have 5 initial terms. To answer our question of what goes in the slot we take 5=2*2+1 as our decomposition. Now that we have a decomposition we can apply our function:

F(x(5)) = F(x(2*2+1)) 2x[2] + 1(x[3] - x[2]).

The thing is, for Python to do this it has to know how to decompose each number. So it knows 2 is fixed, and knows 2*3 is too much and so chooses 2*2.Then it has to know this is too little and add remainder 1. Only once it'sdone this can it actually grab n = 5. That is, it can run the function. It seems clear that once it knows how to do this it can just run through every n in our range, but I'm really not sure how to program the meat of thisfunction.

Now to answer some questions: Is x a function? A list? A number? x[n] is essentially a list.

What do you mean when you say "values of an input string"? What's the signature of Phi_m?

The function acting on this list takes in a single element of the list, gives us a decomposition of the number somehow, and then applies the 'formula'you see above. In this sense it is more of a two step algorithm.

To give another example, say we want to apply psi_2 to 0,1,2,2. Then we have an output of length (3+1)2-1=7. F(7)=F(2*3+1) = 2x[3] + 1(x[4] - x[3]). As we can see, we are missing x[4] (remember 0 doesn't count as a term). So we actually need to stop our calculation one shy of the 7 terms we 'should' have. Hence, although we actually want 7 terms the program really only needs to give 6 terms, the other term can be hand calculated, or the user can append one extra term to the input string 0,1,2,2 and run the program again.

Please let me know if this is unclear. I will certainly continue revising until it makes sense to those reading.
 
J

Joshua Landau

Please let me know if this is unclear. I will certainly continue revising until it makes sense to those reading.

Can you summarize what your question is? Leave aside the details of
the function, just explain what thing in particular you aren't able
to do.
 
C

CTSB01

Can you summarize what your question is? Leave aside the details of

the function, just explain what thing in particular you aren't able

to do.

Hi Joshua,

I actually managed to find a certain block like this:

def phi_m(x, m):
.... rtn = []
.... for n2 in range(0, len(x) * m - 2:
.... n = n2 / m
.... r = n2 - n * m
.... rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
.... print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
.... rtn

However, I am getting the error "expected an indented block" on line two. Any idea why?
 
G

Gary Herron

Can you summarize what your question is? Leave aside the details of

the function, just explain what thing in particular you aren't able

to do.
Hi Joshua,

I actually managed to find a certain block like this:

def phi_m(x, m):
... rtn = []
... for n2 in range(0, len(x) * m - 2:
That 'for' line has miss-matched parentheses.
... n = n2 / m
... r = n2 - n * m
... rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
... print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
... rtn

However, I am getting the error "expected an indented block" on line two. Any idea why?
 
C

CTSB01

Hi Joshua,

I actually managed to find a certain block like this:

def phi_m(x, m):
... rtn = []
... for n2 in range(0, len(x) * m - 2:

That 'for' line has miss-matched parentheses.
... n = n2 / m
... r = n2 - n * m
... rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
... print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
... rtn

However, I am getting the error "expected an indented block" on line two. Any idea why?





--

Dr. Gary Herron

Department of Computer Science

DigiPen Institute of Technology

(425) 895-4418

Hi Gary,

I fixed that issue, but I still end up with the same error. Specifically:


File "<pyshell#9>", line 2
... rtn = []
^
IndentationError: expected an indented block
 
I

Ian Kelly

File "<pyshell#9>", line 2
... rtn = []
^

The "..." is the continuation prompt from the interactive interpreter, not
part of the code. Don't paste it into Python.
 
C

CTSB01

  File "<pyshell#9>", line 2
    ...   rtn = []

The "..." is the continuation prompt from the interactive interpreter, not part of the code. Don't paste it into Python.

Thanks Ian. That worked regarding that issue. Now I have an 'invalid syntax' issue unfortunately.
rtn = []
for n2 in range(0, len(x)*m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
rtn

on the line print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn Is it something obvious?
 
I

Ian Kelly

Thanks Ian. That worked regarding that issue. Now I have an 'invalid syntax' issue unfortunately.
rtn = []
for n2 in range(0, len(x)*m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
rtn

on the line print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn Is it something obvious?

Are you using Python 2 or 3? "print" has changed from a statement to
a function, so the above syntax would be invalid in Python 3.
 
I

Ian Kelly

Thanks Ian. That worked regarding that issue. Now I have an 'invalid syntax' issue unfortunately.
def phi_m(x,m):
rtn = []
for n2 in range(0, len(x)*m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
rtn

on the line print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn Is it something obvious?

Are you using Python 2 or 3? "print" has changed from a statement to
a function, so the above syntax would be invalid in Python 3.

Note also that in Python 3 you should change the line "n = n2 / m" to
"n = n2 // m" because the syntax for integer division has also
changed.

And regardless of your Python version, the last line should probably
be "return rtn", not just "rtn".
 
D

Dave Angel

File "<pyshell#9>", line 2
... rtn = []

The "..." is the continuation prompt from the interactive interpreter, not part of the code. Don't paste it into Python.

Thanks Ian. That worked regarding that issue. Now I have an 'invalid syntax' issue unfortunately.
rtn = []
for n2 in range(0, len(x)*m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
rtn

on the line print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn Is it something obvious?

It's only obvious if you're using Python 3.x. You have forgotten the
parentheses in the call to the print() function.

On the other hand, if this is Python 2.x, I have no idea. Next time,
please paste the actual error, not paraphrased. The error message
includes a traceback. and a pointer to where in the line the error was
detected. If it's pointing at the end of the second token, you must be
running Python 3.x

And since you're using that annoying googlegroups, see this:

http://wiki.python.org/moin/GoogleGroupsPython
 
C

CTSB01

Thanks Ian. That worked regarding that issue. Now I have an 'invalid syntax' issue unfortunately.

def phi_m(x,m):
rtn = []
for n2 in range(0, len(x)*m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
rtn

on the line print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn Is it something obvious?
Are you using Python 2 or 3? "print" has changed from a statement to
a function, so the above syntax would be invalid in Python 3.



Note also that in Python 3 you should change the line "n = n2 / m" to

"n = n2 // m" because the syntax for integer division has also

changed.



And regardless of your Python version, the last line should probably

be "return rtn", not just "rtn".

Thanks! I'm using 3.3.2. As I'm new to this, do you think it's a better idea to jump to 3.3.2 or stick with 2.7? I, for all intents and purposes, know neither.
 
C

CTSB01

It's only obvious if you're using Python 3.x. You have forgotten the
parentheses in the call to the print() function.


On the other hand, if this is Python 2.x, I have no idea. Next time,

please paste the actual error, not paraphrased. The error message

includes a traceback. and a pointer to where in the line the error was

detected. If it's pointing at the end of the second token, you must be

running Python 3.x
And since you're using that annoying googlegroups, see this:

http://wiki.python.org/moin/GoogleGroupsPython

Hi Dave,

There aren't any emails in the Cc slot so I imagine that part is fine, I will definitely edit the extra quotes though I made the mistake of thinking it was just google being google. For reference , I'm running Python 3.x. I'll try out putting the quotes around it. The full code is:
rtn = []
for n2 in range(0, len(x)*m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
rtn

SyntaxError: invalid syntax

where the second apostrophe in 'n2 =' is marked in orange. Thanks to everyone who's helped out so far, hopefully with some experience I'll be able sort out any syntax issues that come my way.
 
D

Dave Angel

Hi Dave,

There aren't any emails in the Cc slot so I imagine that part is fine, I will definitely edit the extra quotes though I made the mistake of thinking it was just google being google.

Exactly. And remember, the list is comp.lang.python, while googlegroups
has tried to pre-empt it by bridging. Most of us get to it either
through the nntp server at gmane.org or via email subscription at
(e-mail address removed)

For reference , I'm running Python 3.x.
I'll try out putting the quotes around it.

Parentheses, not quotes. print() is a function in 3.x
The full code is:
rtn = []
for n2 in range(0, len(x)*m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print 'n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn
rtn

SyntaxError: invalid syntax

where the second apostrophe in 'n2 =' is marked in orange. Thanks to everyone who's helped out so far, hopefully with some experience I'll be able sort out any syntax issues that come my way.
Don't paraphrase. Just copy/paste it into your email message. And I'm
assuming you know to run things from the terminal window, and not from
IDLE or something else that messes up the error messages. Your comment
about 'orange' doesn't sound promising.

As Ian pointed out, you have no return value in this function. You
calculate something called 'rtn', but never use it. The last line
accomplishes nothing, since rtn is neither assigned nor returned, nor
passed nor... You probably wanted:

return rtn
 
C

CTSB01

Thanks for the alternative links, I'll use gmane.org as an access point next time.
Don't paraphrase. Just copy/paste it into your email message. And I'm

assuming you know to run things from the terminal window, and not from

IDLE or something else that messes up the error messages. Your comment

about 'orange' doesn't sound promising.



As Ian pointed out, you have no return value in this function. You

calculate something called 'rtn', but never use it. The last line

accomplishes nothing, since rtn is neither assigned nor returned, nor

passed nor... You probably wanted:



return rtn

Does something like

def phi_m(x, m):
rtn = []
for n2 in range(0, len(x) * m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print ('n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn)
return rtn

look right?

It doesn't seem to have any errors. However, I do receive the following error when trying to implement an x after having defined phi:
x = [0, 1, 1, 2, 3]
phi_m(x, 2)
Traceback (most recent call last):
File "<pyshell#6>", line 1, in <module>
phi_m(x, 2)
File "<pyshell#2>", line 6, in phi_m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
TypeError: list indices must be integers, not float
 
D

Dave Angel

Does something like

def phi_m(x, m):
rtn = []
for n2 in range(0, len(x) * m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print ('n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn)
return rtn

look right?

No, as Ian has pointed out, you need to use the // operator in Python 3
if you want to get integer results. So it'd be n = n2 // m

However, even better is to use the divmod() function, which is intended
for the purpose:

n, r = divmod(n2, m)
It doesn't seem to have any errors. However, I do receive the following error when trying to implement an x after having defined phi:
x = [0, 1, 1, 2, 3]
phi_m(x, 2)
Traceback (most recent call last):
File "<pyshell#6>", line 1, in <module>
phi_m(x, 2)
File "<pyshell#2>", line 6, in phi_m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
TypeError: list indices must be integers, not float

That will be fixed if you correct the code as I described, so you'll get
integers.

There is a Brezenham algorith that might accomplish this whole function
more accurately, or more efficiently. But I'd have to re-derive it, as
it's been about 30 years since I used it. And chances are that the
efficiencies it brought to machine code won't matter much here.
 
F

Fábio Santos

Thanks for the alternative links, I'll use gmane.org as an access point next time.
Don't paraphrase. Just copy/paste it into your email message. And I'm

assuming you know to run things from the terminal window, and not from

IDLE or something else that messes up the error messages. Your comment

about 'orange' doesn't sound promising.



As Ian pointed out, you have no return value in this function. You

calculate something called 'rtn', but never use it. The last line

accomplishes nothing, since rtn is neither assigned nor returned, nor

passed nor... You probably wanted:



return rtn

Does something like

def phi_m(x, m):
rtn = []
for n2 in range(0, len(x) * m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print ('n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn)
return rtn

look right?

It doesn't seem to have any errors. However, I do receive the following
error when trying to implement an x after having defined phi:
x = [0, 1, 1, 2, 3]
phi_m(x, 2)
Traceback (most recent call last):
File "<pyshell#6>", line 1, in <module>
phi_m(x, 2)
File "<pyshell#2>", line 6, in phi_m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
TypeError: list indices must be integers, not float

When you think about it, it makes sense. If you have a list, say,

[2, 5, 1]

You can say, I want the first item (0) or the third item(2) but never, the
one-and-a-halfeth (0.5) item. Python only accepts integer values when
accessing list items.

To access list items, convert your index into an integer value.
 
C

CTSB01

Thanks for the alternative links, I'll use gmane.org as an access pointnext time.


Does something like

def phi_m(x, m):
          rtn = []
          for n2 in range(0, len(x) * m - 2):
            n = n2 / m
            r = n2 - n * m
            rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
            print ('n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn)
          return rtn
look right?
It doesn't seem to have any errors.  However, I do receive the following error when trying to implement an x after having defined phi:
x = [0, 1, 1, 2, 3]
phi_m(x, 2)
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    phi_m(x, 2)
  File "<pyshell#2>", line 6, in phi_m
    rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
TypeError: list indices must be integers, not float

When you think about it, it makes sense. If you have a list, say,

[2, 5, 1]

You can say, I want the first item (0) or the third item(2) but never, the one-and-a-halfeth (0.5) item. Python only accepts integer values when accessing list items.

To access list items, convert your index into an integer value.

Thanks Fabio. Is there a statement that lets me specify that I only need it to take the integer values?
 
C

CTSB01

On 07/18/2013 10:16 PM, CTSB01 wrote:
Does something like

def phi_m(x, m):
for n2 in range(0, len(x) * m - 2):
n = n2 / m
r = n2 - n * m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
print ('n2 =', n2, ': n =', n, ' r =' , r, ' rtn =', rtn)
return rtn
look right?

No, as Ian has pointed out, you need to use the // operator in Python 3

if you want to get integer results. So it'd be n = n2 // m

However, even better is to use the divmod() function, which is intended

for the purpose:



n, r = divmod(n2, m)
It doesn't seem to have any errors. However, I do receive the following error when trying to implement an x after having defined phi:
x = [0, 1, 1, 2, 3]
phi_m(x, 2)
Traceback (most recent call last):
File "<pyshell#6>", line 1, in <module>
phi_m(x, 2)
File "<pyshell#2>", line 6, in phi_m
rtn.append(m * x[n] + r * (x[n + 1] - x[n]))
TypeError: list indices must be integers, not float


That will be fixed if you correct the code as I described, so you'll get

integers.

There is a Brezenham algorith that might accomplish this whole function

more accurately, or more efficiently. But I'd have to re-derive it, as

it's been about 30 years since I used it. And chances are that the

efficiencies it brought to machine code won't matter much here.

Thanks Dave, I'll take a look at that.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
474,044
Messages
2,570,388
Members
47,052
Latest member
ketan

Latest Threads

Top