Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Task 8 compare results
#1
although these test cases are easily verified with a calculator, here is a test script for completeness.

create test script test8.sh with the following

Code:
#!/bin/bash
echo "(21 42)" > results8.txt
echo "(21 42)" > task8.args
scam -r task8.scm task8.args >> results8.txt
echo "(1 2)" >> results8.txt
echo "(1 2)" > task8.args
scam -r task8.scm task8.args >> results8.txt
echo "(2 4)" >> results8.txt
echo "(2 4)" > task8.args
scam -r task8.scm task8.args >> results8.txt
echo "(15 65)" >> results8.txt
echo "(15 65)" > task8.args
scam -r task8.scm task8.args >> results8.txt
echo "(124 642)" >> results8.txt
echo "(124 642)" > task8.args
scam -r task8.scm task8.args >> results8.txt
cat results8.txt


allow it to be executed with the command
Code:
chmod u+x test8.sh

run it with

Code:
./test8.sh


My results:

Code:
(21 42)
half of 21 is 10
half of 42 is 21
21 squared is 441
42 squared is 1764
882
(1 2)
half of 1 is 0
half of 2 is 1
1 squared is 1
2 squared is 4
2
(2 4)
half of 2 is 1
half of 4 is 2
2 squared is 4
4 squared is 16
8
(15 65)
half of 15 is 7
half of 65 is 32
15 squared is 225
65 squared is 4225
975
(124 642)
half of 124 is 62
half of 642 is 321
124 squared is 15376
642 squared is 412164
79608

Also, did anyone else find implementing the "halve" function surprisingly tricky?

I got something that's O( (lg n)^2 ).
Reply
#2
There's nothing surprising about how "tricky" the halve function is. Still don't know how to do it. I'm absolutely dying at the hand of Lusth's demand for mathmatical nimbleness, which I admit is probably useful (if not critical) for being a cool computer scientist, but not my forte at all.
UA ACM Vice President
ACM has bi-weekly meetings Tuesdays at 5:15pm
We're UA's best organization for CS majors (website)
Join us on Slack for all kinds of discussion channels (including one for CS403)
Reply
#3
(09-02-2017, 05:10 AM)davidmccoy Wrote: There's nothing surprising about how "tricky" the halve function is. Still don't know how to do it. I'm absolutely dying at the hand of Lusth's demand for mathmatical nimbleness, which I admit is probably useful (if not critical) for being a cool computer scientist, but not my forte at all.

I don't even know if my implementation is correct because I didn't come up with a recurrence equation for halve that's "analogous to the square recurrence equation". My approach is something that involves finding half the value of the leading bit recursively. Since there doesn't seem to be a way to write down its recurrence as nicely as the one for the square recurrence, I'm almost certain it's not whatever the Babylonians used.
Reply
#4
I feel like we shouldn't be performing a bit shift in order to divide... Idk what to do atm though expect to continue to stare emptily between my monitor and pen and paper.

I cannot for the life of me come up with a recurrence that is sublinear. Everything I come up with for halve(i) ends up moving i only by a constant, making it overall linear like square and zarp. For it to be sublinear, i would have to change by some factor, but I can't use anything but addition and subtraction...
UA ACM Vice President
ACM has bi-weekly meetings Tuesdays at 5:15pm
We're UA's best organization for CS majors (website)
Join us on Slack for all kinds of discussion channels (including one for CS403)
Reply
#5
(09-02-2017, 06:59 AM)davidmccoy Wrote: I feel like we shouldn't be performing a bit shift in order to divide... Idk what to do atm though expect to continue to stare emptily between my monitor and pen and paper.

I cannot for the life of me come up with a recurrence that is sublinear. Everything I come up with for halve(i) ends up moving i only by a constant, making it overall linear like square and zarp. For it to be sublinear, i would have to change by some factor, but I can't use anything but addition and subtraction...

I don't use a bit shift operation, but rather I do a series of checks while doubling starting from 1.
More clearly, the value of the leading bit is 2^i. To find that i, you can keep doubling [using something like (+ x x)] and check to see if you have exceeded the value of the input number.
However, since I want half of 2^i, I actually do the check on the value of the next step, so that I can return 2^(i-1) without dividing by 2.
I use a wrapper function to recursively do this to the remainder of the number until the input number < 2, which is equivalent to ignoring the last bit.
Summing up these values, I have half the value of the original input number.

------------------------------------
Edit: (Note on run time)
This should be O( (lg n)^2 ) since there are at most (lg n) non-zero bits, and for each non-zero bit i, I spend O(i) time determining it. In the worst case, all the bits are 1, so the runtime is the sum of i from 1 to (lg n), which is O( (lg n)^2 ) by Gauss's formula.
Reply
#6
(09-02-2017, 07:09 AM)james_h Wrote:
(09-02-2017, 06:59 AM)davidmccoy Wrote: I feel like we shouldn't be performing a bit shift in order to divide... Idk what to do atm though expect to continue to stare emptily between my monitor and pen and paper.

I cannot for the life of me come up with a recurrence that is sublinear. Everything I come up with for halve(i) ends up moving i only by a constant, making it overall linear like square and zarp. For it to be sublinear, i would have to change by some factor, but I can't use anything but addition and subtraction...

I don't use a bit shift operation, but rather I do a series of checks while doubling starting from 1.
More clearly, the value of the leading bit is 2^i. To find that i, you can keep doubling [using something like (+ x x)] and check to see if you have exceeded the value of the input number.
However, since I want half of 2^i, I actually do the check on the value of the next step, so that I can return 2^(i-1) without dividing by 2.
I use a wrapper function to recursively do this to the remainder of the number until the input number < 2, which is equivalent to ignoring the last bit.
Summing up these values, I have half the value of the original input number.

I mean that sounds basically like shifting the bits to the right with math. Which is super smart. I'm not sure if there's some other grander concept we're supposed to be grasping, but it's killing me. No one else on Google has apparently ever tried to solve this problem O_o. I guess this is the type of guess and check we'd want to perform, but it's completely unrelated to the square recurrence (except for the fact that, since they are both recursive functions, they can be described by a recurrence?).
UA ACM Vice President
ACM has bi-weekly meetings Tuesdays at 5:15pm
We're UA's best organization for CS majors (website)
Join us on Slack for all kinds of discussion channels (including one for CS403)
Reply
#7
(09-02-2017, 07:13 AM)davidmccoy Wrote:
(09-02-2017, 07:09 AM)james_h Wrote:
(09-02-2017, 06:59 AM)davidmccoy Wrote: I feel like we shouldn't be performing a bit shift in order to divide... Idk what to do atm though expect to continue to stare emptily between my monitor and pen and paper.

I cannot for the life of me come up with a recurrence that is sublinear. Everything I come up with for halve(i) ends up moving i only by a constant, making it overall linear like square and zarp. For it to be sublinear, i would have to change by some factor, but I can't use anything but addition and subtraction...

I don't use a bit shift operation, but rather I do a series of checks while doubling starting from 1.
More clearly, the value of the leading bit is 2^i. To find that i, you can keep doubling [using something like (+ x x)] and check to see if you have exceeded the value of the input number.
However, since I want half of 2^i, I actually do the check on the value of the next step, so that I can return 2^(i-1) without dividing by 2.
I use a wrapper function to recursively do this to the remainder of the number until the input number < 2, which is equivalent to ignoring the last bit.
Summing up these values, I have half the value of the original input number.

I mean that sounds basically like shifting the bits to the right with math. Not sure if there's some grander concept we're supposed to be grasping, but it's killing me. No one else on Google has apparently ever tried to solve this problem O_o

It is indeed essentially a bit-shift, but the point is that I use nothing but addition, subtraction, and conditionals and that it runs in sub-linear time.
Reply
#8
Suppose I want to halve 515. It is easy to find half of 512 (which is 256) via doubling, yielding a log process. All that remains then is finding half of 3.


Also, I'm pretty sure a solution (not my solution) is out there on the interwebs. I've given this problem before and more than one student found this alternative solution.
Reply
#9
(09-02-2017, 12:56 PM)lusth Wrote: Suppose I want to halve 515. It is easy to find half of 512 (which is 256) via doubling, yielding a log process. All that remains then is finding half of 3.


Also, I'm pretty sure a solution (not my solution) is out there on the interwebs. I've given this problem before and more than one student found this alternative solution.

This is the method I am currently implementing for my halving function, and I received the message in my assignment results "too many recursive calls were made".

More specifically, the test being run was "trying to halve 1073741821..." to which my program returned the correct value but was marked wrong because "too many recursive calls were made (394 pushes)".

Any idea what could cause this?
Reply
#10
Halve is supposed to be iterative. Is yours iterative?
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)