473,326 Members | 2,110 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,326 software developers and data experts.

how to prove 'roundup' arithmetic

Hi,
#define roundup(x,n) (((x)+((n)-1))&(~((n)-1)))
This macro is to set x align with n. But how to prove the arithmetic?
Abviously, I can use the value to check it. What's the else?

Thanks
Eirc

Jun 1 '06 #1
3 4789
On 2006-06-01, jo********@gmail.com <jo********@gmail.com> wrote:
Hi,
#define roundup(x,n) (((x)+((n)-1))&(~((n)-1)))
This macro is to set x align with n. But how to prove the arithmetic?
Abviously, I can use the value to check it. What's the else?

"Abviously". That's a new one. A and O are at opposite ends of the
keyboard. Since you appear not to speak English as a first language,
remember that the word is "obviously".

This question is beyond the realm of clc. You should check on one
of the algorithm-related groups. Try comp.programmer.

--
Andrew Poelstra < http://www.wpsoftware.net/blog >
To email me, use "apoelstra" at the above address.
You can lead a blind man to water but you can't make him chug it.
Jun 1 '06 #2
jo********@gmail.com said:
Hi,
#define roundup(x,n) (((x)+((n)-1))&(~((n)-1)))
This macro is to set x align with n. But how to prove the arithmetic?
Abviously, I can use the value to check it. What's the else?


Given that n is a power of 2, ~(n - 1) will zero out the low log2(n) bits.

Take n = 16, for example, and feed it 0 for x. You'll end up with 15 & ~15,
which is clearly 0. That's because 15 is 0000...00001111, and ~...00001111
is ...11110000, so the AND-mask wipes out those bottom few bits.

Now take n = 16 and feed it 1 for x. This time, you'll end up with 16 & ~15.
This is:

......00000010000
......11111110000 AND
----------------
......00000010000

which is 16. The leftmost bits of the ~15 expression preserve the leftward
bits in (x + n - 1), and the rightmost bits blow away the low bits. The + n
- 1 part is to ensure that x is never decreased as a result of the
rounding. Adding n would be too much, because it would move a value that is
already aligned; and adding n - 2 would be insufficient, because it would
fail to lift, say, a 1 to the next boundary up. But n - 1 is just right.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jun 1 '06 #3
On 1/6/06 05:04, Andrew Poelstra wrote:
On 2006-06-01, jo********@gmail.com <jo********@gmail.com> wrote:

Abviously, I can use the value to check it. What's the else?

"Abviously". That's a new one. A and O are at opposite ends of the
keyboard.

http://www.klippert.com/tcc/blog/pics/Dvorak.jpg

;-)
Jun 1 '06 #4

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

Similar topics

1
by: Donald 'Paddy' McCarthy | last post by:
For Hardware design we jave a very high cost associated with releasing a design for manufacturing (around $1M), so one of the things we do is simulate like crazy, and graph bugs found and bugs...
4
by: Phoon Chee Keong | last post by:
Is that a formula in vb.net like Ms Excel? Currently my Excel formula is "=(((ROUNDUP(I30/3000,0)+1)*G30)/1000)+((ROUNDUP(G30/10000,0))*I30/1000)", but in vb.net how to write. Any idea? ...
0
by: Richard Jones | last post by:
I'm proud to release this, the 1.1.1 release of Roundup. Fixed in this release: - failure with browsers not sending "Accept-Language" header (sf bugs 1429646 and 1435335) - translate class...
158
by: Giovanni Bajo | last post by:
Hello, I just read this mail by Brett Cannon: http://mail.python.org/pipermail/python-dev/2006-October/069139.html where the "PSF infrastracture committee", after weeks of evaluation, recommends...
4
by: Richard Jones | last post by:
I'm proud to release version 1.1.3 of Roundup. Feature: - supports Python 2.5, including the sqlite3 module - full timezone support (sf patch 1465296) - handle connection loss when responding...
1
by: bcannon | last post by:
At the beginning of the month the PSF Infrastructure committee announced that we had reached the decision that JIRA was our recommendation for the next issue tracker for Python development....
0
by: Richard Jones | last post by:
I'm proud to release version 1.3.3 of Roundup. Fixed in 1.3.3: - If-Modified-Since handling was broken - Updated documentation for customising hard-coded searches in page.html - Updated...
2
by: carlistixx | last post by:
Hi, I'm using the roundup issue tracker (http://roundup.sourceforge.net) which uses smtplib to send mail. It all worked until we moved to a hosted Exchange MTA. The hosting provider requires the...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
1
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: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
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...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
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
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

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.