{"id":32363,"date":"2006-02-07T10:00:08","date_gmt":"2006-02-07T10:00:08","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2006\/02\/07\/viewing-function-composition-as-transformation-of-the-domain\/"},"modified":"2006-02-07T10:00:08","modified_gmt":"2006-02-07T10:00:08","slug":"viewing-function-composition-as-transformation-of-the-domain","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20060207-08\/?p=32363","title":{"rendered":"Viewing function composition as transformation of the domain"},"content":{"rendered":"

\nA lot of formulas you encounter in computer science can be\nviewed as function composition.\nLet’s start with the simple problem of rounding integers down to the\nnearest multiple of some positive constant.\nThe formula for this should be relatively easy for you to produce:\n<\/p>\n

\nround_down(n, m) = floor_div(n, m) * m\n<\/p><\/blockquote>\n

\nwhere floor_div<\/code> returns the largest integer\nless than or equal to n\/m.\nIf n≥0 and m>0, then floor_div(n,m) = n\/m<\/code>\nwhere \/<\/code> is the C integer division operator.\n<\/p>\n

\nBut what if you want to round up?\nTake a look at the difference between rounding up and rounding down,\nsay, using multiples of four for concreteness.\n<\/p>\n\n\n\n\n
<\/td>\n 0<\/td>\n 1<\/td>\n 2<\/td>\n 3<\/td>\n 4<\/td>\n 5<\/td>\n 6<\/td>\n 7<\/td>\n 8<\/td>\n 9<\/td>\n10<\/td>\n11<\/td>\n12<\/td>\n<\/tr>\n
round_down<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n4<\/td>\n4<\/td>\n4<\/td>\n4<\/td>\n8<\/td>\n8<\/td>\n8<\/td>\n8<\/td>\n12<\/td>\n<\/tr>\n
round_up<\/td>\n0<\/td>\n4<\/td>\n4<\/td>\n4<\/td>\n4<\/td>\n8<\/td>\n8<\/td>\n8<\/td>\n8<\/td>\n12<\/td>\n12<\/td>\n12<\/td>\n12<\/td>\n<\/tr>\n<\/table>\n

\nThe round_up<\/code> table is just the\nround_down<\/code> table shifted left three places.\nThe mathematical way of shifting the table heading is by\nmanipulating the domain,\nin this case, by adding three.\nIn other words, don’t think of adding three as a vertical operation\n<\/p>\n\n\n\n\n
 0<\/td>\n 1<\/td>\n 2<\/td>\n 3<\/td>\n 4<\/td>\n 5<\/td>\n 6<\/td>\n 7<\/td>\n 8<\/td>\n 9<\/td>\n10<\/td>\n11<\/td>\n12<\/td>\n<\/tr>\n
+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n+3<\/td>\n<\/tr>\n
3<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n7<\/td>\n8<\/td>\n9<\/td>\n10<\/td>\n11<\/td>\n12<\/td>\n13<\/td>\n14<\/td>\n15<\/td>\n<\/tr>\n<\/table>\n

\nbut rather as a horizontal one:\n<\/p>\n\n\n\n\n
 0<\/td>\n 1<\/td>\n 2<\/td>\n 3<\/td>\n 4<\/td>\n 5<\/td>\n 6<\/td>\n 7<\/td>\n 8<\/td>\n 9<\/td>\n10<\/td>\n11<\/td>\n12<\/td>\n<\/tr>\n
<- move left three spaces<\/td>\n<\/tr>\n
3<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n7<\/td>\n8<\/td>\n9<\/td>\n10<\/td>\n11<\/td>\n12<\/td>\n13<\/td>\n14<\/td>\n15<\/td>\n<\/tr>\n<\/table>\n

\n(Sorry, I’m too lazy to cook up the appropriate VML diagram.\nUse your imagination and pretend that there is an arrow from the\n“3” in the top row to the “3” in the bottom row,\nsimilarly from the “4” in the top row to the “4” in the bottom row,\nand so on.)\n<\/p>\n

\nNow that you see that the answer is to “move the results” three\nspots to the left,\nyou can read off that the desired formula is\n<\/p>\n

\nround_up(n, 4) = round_down(n + 3, 4)\n<\/p><\/blockquote>\n

\nShifting the domain left and right can be done by addition.\nMultiplication and division let you stretch and shrink it.\nConsider the\n\npuzzle of rounding down to the nearest quarter<\/a>.\nYou already know how to round down to the nearest unit,\nnamely by using the language’s built-in truncation operator.\n<\/p>\n

\n0    1    2    3    4    5    6\n|    |    |    |    |    |    |\n+----+----+----+----+----+----+\n \\___\/\\___\/\\___\/\\___\/\\___\/\\___\/\n   0    1    2    3    4    5\n<\/pre>\n
\nIf only we could divide everything in the diagram by four.\nBut we can!\nTo do this, we transform the problem space into one in which\neverything is four times as big as normal, apply the operation,\nand then convert back to normal size.\n<\/p>\n
\nThose of you who’ve played with a Rubik’s Cube are well familiar\nthis technique:\nIf you have a move that, say, flips two adjacent edges,\nbut you want to flip two edges that aren’t adjacent, you can still\naccomplish this by manipulating the cube until the two edges\nare adjacent, perform the flip move, then undo the steps you performed\nto get the edges adjacent in the first place.\n(This is known as “conjugation” in group theory and is a very handy\ntechnique.)\n<\/p>\n
\nWe’re just doing the same thing with this truncation operation:\nIf we could shrink the truncator a factor of four, it would\ntruncate by quarters.\nBut we don’t know how to shrink the truncator, so we do it\nfrom the other direction:\nStretch the number line, apply the truncator, then shrink it back.<\/p>\n
\n0                   1\n|                   |\n|   1\/4  2\/4  3\/4   |   5\/4  6\/4\n|    |    |    |    |    |    |\n+----+----+----+----+----+----+\n \\___\/\\___\/\\___\/\\___\/\\___\/\\___\/\n   0    1    2    3    4    5\n   0   1\/4  2\/4  3\/4  4\/4  5\/4\n<\/pre>\n
\nThe top line shows the number line stretched by a factor of four.\nThe truncator is still unchanged.\nAnd below it, we shrink the results by a factor of four,\nresulting in our desired rounding down to the nearest quarter.\n<\/p>\n
\nTaking the above diagram and converting it back to a formula:\n<\/p>\n
\nround_down_to_quarter(v) = trunc(v * 4.0) \/ 4.0\n<\/p><\/blockquote>\n
\nThis was probably old hat for most of you,\nbut I think it’s worthwhile seeing how the problem can be\nviewed geometrically.\nIn particular, if you have a reversible operation “f”,\nthen the composition “f-1<\/font><\/sup>\n◦ g ◦ f”\nhas the effect of “reinterpreting g through f-colored glasses”.\nHere, the operation “f” was “multiple by four”\nand “g” was “truncate to nearest integer”.\nPutting them together allowed us to take the truncation operator “g”\nand make it truncate according to a different set of rules.\n<\/p><\/p>\n","protected":false},"excerpt":{"rendered":"
A lot of formulas you encounter in computer science can be viewed as function composition. Let’s start with the simple problem of rounding integers down to the nearest multiple of some positive constant. The formula for this should be relatively easy for you to produce: round_down(n, m) = floor_div(n, m) * m where floor_div returns […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-32363","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
A lot of formulas you encounter in computer science can be viewed as function composition. Let’s start with the simple problem of rounding integers down to the nearest multiple of some positive constant. The formula for this should be relatively easy for you to produce: round_down(n, m) = floor_div(n, m) * m where floor_div returns […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/32363","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=32363"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/32363\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=32363"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=32363"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=32363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}