Jump to content
Banner by ~ Ice Princess Silky

Splashee

User
 View Profile  See their content

  • Posts

    15,544

  • Joined

  • Last visited

 Content Type 

Blog Entries posted by Splashee

  1. Splashee

    Microhoof Equality XP (Build 1620)

    By Splashee,


    Microhoof Equality XP
    Welcome to the world of Equality!

     
    Starlight Glimmer has decided to give out free games in a sweet -easy to use- package called Equality Experience Pack. Microhoof Equality XP is aimed to work on any modern device such as a personal computer or smartphone. Safely running in your favorite web browser, with a click of a link to start:
    http://logotypes.se/equxp/?build=1620
     
    The current build 1620 fixes the previous bugs and glitches that were part of the MLP Forums Pony Dev Jam a while back. One such bug was the enemies in Pac-Pony getting stuck in walls. The biggest fauture of this new build is the horizontal and vertical wrapping of Pac-Pony (where the player and enemies can wrap from one side to the other, seemingly being in two locations at once). The wrapping is endless and adds to the challenge of avoiding enemies trying to hunt you down from a different "screen" even though they are visibly on the same screen as you (they might be several screens away from you, but they can still hit you!).
    4 difficulty modes are supported. The Nightmare Mode difficulty is there to show that players and enemies can move faster than a single grid unit, but still collide with walls and pick up items, or collide with themselves.

    PonyTris has been fixed as well, and the clearing of lines animation is now symmetrical:
     
     
     
    Screenshots from build 1620:




     
    Under the hood is modern C++ code written by me, compiled to WebAssembly. This has a huge advantage since everything is run at the highest speed in a safe environment of anyone's web browser, but at the same time allows for no visible code to the end user. This is different from earlier web games that are written in JavaScript where code need to be obfuscated to become unreadable to the end user, which adds a huge performance penalty to the games.
    With C++ code compiled, the resources become smaller, faster, and a lot harder to hack or modify. No C++ standard libraries were available, meaning I had to write my own memory allocator, operator new and delete, to support C++ classes with polymorphism.
     
    More games will be added!
  2. Splashee
    The more time passes by, people get nostalgic about the past, about their childhood. Many PC gamers of the late 90s and early 2000 get very nostalgic when they see the CRT shaders applied to their favorite PC emulators. Many remember, but do they remember correctly?
     
    (This applies to old consoles as well, such as Super Nintendo and Sega Genesis). A TV or computer monitor were made of a bulky heavy thing called a CRT. The thing that people remember the most are the scanlines, and that somehow, pixels were more smoother.
    Then there are people who actually repairs CRTs today, and they know everything about how they work, in technical detail. That is cool and all.
    But what about the general public, and this nostalgia factor?
    This is a screenshot from DOOM, through a CRT:

    It's not through a real CRT. It is a PC emulator called DosBox and it uses a popular CRT shader called "lottes" with some custom settings dialed in to please the author of the screenshot.
     
    What's wrong about this above image? Well, it is the scanlines. The shader takes the emulator screen and divides each pixel horizontal rows into scanlines. The scanlines are clearly taller to get the right aspect ratio for the game (probably not). You can see it at the top of the New Game graphics, that the red outline is only one scanline thick. If this was a real computer with a real CRT (where original DOOM was played on), there would be two scanlines instead of one.
    Like we all remembered it?
    Back when the first CRT shader showed up, around 2016, it did it right (with double scanlines, and aspect ratio, and all), and it got me very interested in getting myself the best possible real CRT monitor for my old PC, so that I could see the real thing, and remember the real thing.
     
    Here are some (real) photos that I just took, from my Trinitron 21 inch CRT I bought in 2017, but it is from 1999:

    The "G" in GEAR's top scanline is one pixel height. This is because I am using a high resolution where pixels map to pixels. Thanks to Windows 98, I can do that. But the real thing is below...
     

    Now, this is how DOOM would display its art (I don't have DOOM to test on). The top of the G is now two scanlines. The art in the game is still only one pixel high! it is the CRT doing the thing here!
    What is that green area on the left hand side?
    This is what those emulators and shaders will never be able to fully understand. It is the border. It is outside the range of what can be drawn on. The pixels don't go there, but still, you see there is a border. A single color (green right now, but usually black and invisible), which stretches outside the area the game can draw on, but at the same time, doesn't fill up the entire CRT screen. It is a thing that most people just don't remember. I remember it. I love it.
     
    Do you see all those little dots? Are they pixels? No, they are not pixels. (The technical name is "Shadow Mask"). With them, you get that smooth look that people sometimes associate with "real" pixel art. I am not here to say what is real or not. It is people's own preference how they want to view their art. Clean pixels. Scaled up pixels. Though a CRT. Anything is okay!
    What is most common to remember about old TVs (CRTs) are the scanlines. You can clearly see the scanlines more than any horizontal division of pixels. It is quite easy to count how many pixels there are vertically, but almost impossible to exactly know how many pixels there are horizontally. A CRT is analog, meaning you can stretch the screen using dials usually on the CRT itself, so that it covers more/less area, but the screen doesn't look worse, and pixels don't seem to get uneven, because the CRT is analog, and the output is not digital like the monitor you use right now.
    One last thing, and this is the shut down image from Windows 98, redrawn by me to show one single pixel:

    The white thing in the top-left corner is actually one square pixel in the art. The size of this art is 320x400 pixels. That is a huge vertical size compared to the horizontal size, but the CRT displays the image like if it was 4:3 aspect ratio, and it does it in a way that modern displays just can't do! That's because of the analog nature of a CRT. Now we are back to one pixel per scanline. This is the same screen mode as DOOM used, only hacked to show every scanline, instead of duplicating every scanline twice. DOOM ran in 320x200 (which stretches since that is not a 4:3 aspect ratio), and this mode above runs in 320x400, double the height. Both are displayed in 3:4 aspect ratio, making the pixel art look unique and not the same way it was originally drawn. Yes, game artists had to draw pixel art that would look stretched in the game, so they had to compensate. A round circle would become an ellipse if they just kept it exactly round in the original art.
     
    The border in the above image is black. And because most borders are black, they are forgotten even by emulator authors (which are very wise people!). It saddens me that people don't think it is important just because it isn't currently visible.
     
    If you were a game artist back in the day, you had to draw your art in a way so that it would be displayed correctly in these screen modes (not just computers, but Super Nintendo also had a resolution that was stretched. A Super Mario World sprite you can find online is probably not the same as it was intended to look) . Today, monitors display each pixel as square, and if they try to compensate, the result is blurry ugly pixels, or uneven pixels that break the illusion of the original art. CRT shaders do what they can to... at least get the aspect ratio back. But they do bring back a lot of nostalgia to people, and it is quite fun to see everyone's reaction online as they just think they went back in time, to a simpler, innocent time. A time when things were "better".
     
     
     
  3. Splashee

    (Math) Beating Pythagoras...

    By Splashee,


    Binary Math
    I have watched countless YouTubers and their science videos. One thing they all have in common is the word they keep throwing at their audience:
    "Albert Einstein".
    It is a free word to use, but it somehow bring in revenues.
     
     
     
    In mathematics, we have a similar word: "Pythagoras". Remember him from preschool math? He figured out some great geometry calculations. The most known, and extremely useful, is the Pythagorean theorem.
     
    It goes something like this:
    A right-angled triangle's longest side (called the hypotenuse) length times itself, equals the length of the other two sides of that same triangle times themselves, added together.
    Longest side * Longest side = First side * First side + Second side * Second side
    Pretty clever stuff that YouTubers and school teachers love to teach. But what if you one day say you have beaten that equation? What if you stand up to history, and all those revenues, and simply call your equation something silly, like, I don't know.... Dot? Yea, let's go with Dot.
    Pythagorean theorem is a special case in a much larger (and way more powerful) algorithm, that works in any dimension. It is called: Dot product.
    A silly name, not having as much punch to it to get you anywhere on YouTube.
     
    Let's just see why we need Pythagorean theorem first, so we understand why it is so important. Units and ratios.
    You know that a unit is simply, a thing. You can have this many units of "something". In math, we can say that 1 times "something" is one unit. Or maybe 1 "something". Once we have that defined, we can scale it to any quantity of something by multiply it by that number of quantity.
    1 * 5 = 5.
    1 "something" * 5 = 5 "something".
    You can even go so far to divide one using with a completely different unit, and get a new unit:
    1 kilometer / 1 hour = 1 kilometer/hour (a unit called kilometer per hour, which acts as a derived unit for both speed and velocity).
     
    Pythagorean theorem is used to find the length of a distance. That distance, divided by its length becomes a unit of that very distance. It is a distance that has a direction, and is scalable to any distance!
    For example, if you have a distance of 5. And the length of that distance is also 5, you will get 1 if you take 5 divided by 5. 1 is in this instance the unit! Sound stupid? Yes, but imagine if you have a distance of 10, and the length of it is....... 5? Well, you will know that the unit is 2. Imagine that the unit's name for 1 is bananas and the unit's name for 2 is oranges. Well, you can scale those units up by the numbers you want! If you want 300 oranges, well, 2 * 300 will give you 300 oranges. With distances, they sure have more than just a length. They have a direction! And it is not so easy to find the unit of a direction, so we can figure out the direction itself.
    We need to use a mathematical function called the Square Root together with Pythagorean theorem, to find the length like that. I will get into that later.
     
    But then we have ratios. When you start dividing one side of a right-angled triangle with another side, you will get a ratio. If you for example, take the horizontal (adjacent) side of a right-angled triangle and divide it by the hypotenuse (the longest side), you will get a ratio, which is called the Cosine. There is also a mathematical function called the Cosine of an Angle.
    We all know Angles. We use them all the time. So is Angle a unit or a ratio? I know that Angles are dimensionless. In daily tasks you measure angles using degrees, but in the real world, mathematicians use a unit called Radians. I won't use Radians, or even angles, so don't worry!
     
    Anyways, let's get back to the main problem at hand. We have a 4-dimensional world, and we need to measure the distance between two objects in that world. What do we do?
    Well, if it was a 2-dimensional world, we could use Pythagorean theorem? But we don't. We live in a 3-dimensional world, and so did Pythagoras. However, what about our 4-dimensional world? We need that distance!
    Let's use Cartesian coordinate system: X is the horizontal axis. Y is perpendicular to X (vertical axis). Z is perpendicular to both X and Y. Now we just need a 4th dimension, and let's just say it is called W. So W is perpendicular to all X, Y, and Z. This is outside what our reality can see, and thus, you will never ever be able to imagine it, no matter how hard you try.
    Dot product solves our problem, for any dimensions, even the ones we can't imagine. That's how complicated it is. It is the most difficult equation you will ever read about.
     
    Nah, just kidding. It is very simple:
    Dot product = X * X + Y * Y + Z * Z + W * W.
    That is it. To make it more readable:
    Dot product = (X * X) + (Y * Y) + (Z * Z) + (W * W).
     
    That is for any dimension, so for 2-dimensions, you have:
     
    Dot product = (X * X) + (Y * Y).
    Doesn't it look a lot like Pythagorean theorem? One side times itself plus the other side times itself? And since X is perpendicular to Y, it is basically a right-angled triangle.
    Of by the way, before we move on, let's just talk a short moment about vectors. A vector is a direction and a length, in any dimension. Fine? It is important to understand that a vector is a value for each dimension, to make up the direction and length combined. In 2-dimensions, you could see the hypotenuse as an angle for its direction, and the length being its length. But as a vector, we don't need that angle at all! We just say that X is that many units away from origin, and Y is that many units away from origin, and origin is the start position for that vector. We then have the length and direction all covered!
     
    So what is Dot product, and what can we use it for? Well, except for finding the length of the hypotenuse of a right-angled triangle, we can find the length of any distance in any dimension. Sound good right?
    First, let's explain what Dot product is. It is not a unit! It is a "scalar". It is like that thing you multiply with a unit to get units. Like 1 "something" times 5..... The 5 in this case is a scalar.
    It is a scalar of exactly 2 vectors! One vector Dot another vector. Both vectors must have the same number of dimensions!
     
    The result for Dot Product is: The length of the first vector times, the length of the second vector times, the Cosine of the Angle between them.
    This is extremely powerful, since the answer is the length of both vectors (something we don't know!), and the cosine ratio of the angle between them (which we also don't know!), and by that, also the angle (magical!).
    Dot product gives us the answers to 3 (or 4) things, with just very fast multiplications and additions calculations that anyone can do! If you ever wonder why Matrix-math seems so similar to this, then you know that Dot product is involved there as well!
     
    So back to Pythagoras. What he couldn't see was that his complex ideas that took him his own life time to figure out, only got 1 answer out of Dot Product's 3. And only for 2-dimensions in a 3-dimensional world. Kinda sad when you think about it? Imagine the day when Albert Einstein gets beaten by something as simple, and with a simple name as well? All those poor YouTubers, I feel for them!
     
    So the special case of Pythagorean theorem. Since he is using the same vector twice, he will get the answer from Dot product: The length of the first vector times, the length of that same vector, times the Cosine of the Angle between them which is 1 since the angle of two equal vectors is 0.
    The answer is then, the length times the length times 1. You need a way to find the length, so you must divide the product with 1 (for the Cosine part) which does nothing, and then divide that product with the length of the first vector (which you don't know, but you know it is the square) so you will use Square Root to get the answer.
    An example:
    A 1-dimensional vector's real length = 5, and the Cosine of the Angle between that same vector is 1:
    5 * 5 * 1 = 25.
    You want to know that 5 is the length, but how do you get 5 from 25? Look up Square Root if you don't know what it is. Pythagoras used Square Root as well.
     
    So, Dot product works very well for many thing. Such as finding if a vector is intersecting another vector and at what distance (the intersection point), and if a vector is facing another vector or not by just looking at the sign from the result of the Cosine. Also, Cosine in itself is directly useful for calculating how much light is reflected off of a surface, if you know the light's vector, and the normal (perpendicular vector) of the surface. If you want the angles, you need to use the ArcCosine math function which translates the ratio back to the angle in Radians, and you can translate Radians into Degrees.
    Dot product is also used for projection. You can project a 2D shadow from a 3D object. If you want to project a vector onto another vector, you just need to find the length of the first vector (using Dot product on itself and Square Root the result, divide that result off every dimension for that vector), which makes it a unit vector, and then Dot product that unit vector with the other vector to project it along that vector's direction directly. At least that's how much I can store in my head right now.
    Dot product is not completely alone in this world. There is another important one called Cross product, which results in a perpendicular vector, which is required to find those normals I was talking about in the section above. Cross product is almost too magical to imagine, so let's not. Cross product doesn't work in 2-dimensions so Pythagoras didn't stand a chance!
     
    And that's a story you can tell your math teacher! "How I beat Pythagoras". YouTube video pending since I mentioned Einstein twice, money!!
  4. Splashee
    In my previous blog about binary division, I stated the first rule about doing division is being "an Exception" if the divisor is equal to 0. This is different from returning a result. No longer will the CPU of the computer be executing normally after such an operation:
    Quotient = dividend / 0
    Modulus = dividend % 0
    The operation will return a quotient and remainder of a binary division (two results). If the absolute (positive) divisor is higher than the absolute (positive) dividend, the quotient will always be 0, and the remainder equals the signed (the original) dividend.
    The quotient will be negative if the sign of dividend and divisor was different. This can be done with a bitwise XOR (Exclusive OR) check:
    Is Negative Quotient = (Dividend AND signbit) XOR (Divisor AND signbit)
    The modulus will be negative if dividend was negative.
    The division itself is done on the absolute value of dividend and the absolute value of divisor.
     
    So those are all fine. However, dividing by 0 is not. It simply must not happen. Here is why:
    In order to find out what dividing by 0 means, one must first try different approaches:
    If multiplication is a series of addition, then division can be seen as a series of subtractions (not always true). If we try to subtract the divisor from dividend to reach 0, the number of times we do so will yield the quotient (hopefully). If we try to do it with a divisor of 0, we will keep subtracting forever until we have reached 0. The quotient can then be seen as infinite (∞) as the subtraction goes on for infinite times.
    However, there are more ways to look at division. Like making the divisor smaller until it is close to 0, or 0, and look at the results:
    1 / 1 = 1
    1 / 0.1 = 10
    1 / 0.01 = 100
    1 / 0.001 = 1000
    ...
    1 / 0 = ∞
    So a division by 0 equals ∞ (infinity) then? Well, let's try another dividend:
    2 / 1 = 2
    2 / 0.1 = 20
    2 / 0.01 = 200
    2 / 0.001 = 2000
    2 / 0 = ∞
    So 1 / 0 equals ∞ and 2 / 0 equals ∞. Then, from this equation, 1 equals 2 then? 1 = 2... That's absolutely fail! Let's try this:
    1 / -1 = -1
    1 / -0.1 = -10
    1 / -0.01 = -100
    1 / -0.001 = -1000
    ...
    1 / 0 = -∞
    Now division by 0 equals -∞. There is no number that makes sense for these results!
    The answer to division by 0 is "undefinable". Computers must always work with "definable", so the correct thing to do is tell the CPU to enter an exception "Divide By Zero". From there, someone (not us) will know what to do, or the computer will have to be turned off and turned on again to get the CPU out of that exception.
    Everyone makes mistakes, and programmers will sometime divide by 0, even when they didn't plan to. Such a mistake costs the most. When the computer runs out of precision for very low floating point numbers, the number will more than likely be a 0.0, causing a "Divide By Zero" exception.
    A CPU will, during an exception, execute code to find a way to fix the original problem that led to the exception happening. That code must not do an exception. If the exception code divides by 0, a "Double Fault" exception will occur. If during that exception, yet another division by 0 happens, the CPU enters a "Triple Fault" exception and shuts down. (That means what it means. If the CPU of the computer is in charge of a critical operation, such as a nuclear facility or worse, that's truly the end)
  5. Splashee

    Binary Math (Division)

    By Splashee,


    Binary Math
    Previously, we talked about multiplication and Bitwise Shift Left. It was quite fun to figure out how to do multiplication since basically all CPUs support it (all had to be figured out without direct help).
    Division however, is not supported by all CPUs, most noted by the modern handheld console Gameboy Advance that required a lot of division, but had no support for it.
    The C and C++ standard requires the division and modulo operators, meaning they must be emulated by the compiler if hardware doesn't provide them. That's where I got to learn how to do it. I did not figure this out. In fact, I used this division code to figure out multiplication (check it out in my previous blog entry).
    There are two types of division, one being the normal signed division. The other one is the one I will talk about since it is less work. The unsigned division: Meaning both dividend and divisor must be positive values. If they are negative, they are treated as unsigned (very large positive numbers).
    The result of a division yields a quotient and a remainder (two answers). Multiplying the resulting quotient by the original divisor, and then adding the resulting remainder, equals the original dividend.
    Quotient = Dividend / Divisor
    Modulus = Dividend % Divisor
    (Where / is the divide operator and % is the modulo operator, both being the result of the single division)
    Division can under no circumstances be allowed if the divisor is 0. This should immediately throw an exception. Division by 0 is simply forbidden. That is true for all math, not just binary.
    If divisor is higher than dividend, then quotient is always 0, and the modulus (remainder) is dividend. Those are all the special conditions to deal with before actually doing the division.
     
    Binary division is done with power-of-2 values. You can shift all the bits of a value right by 1 bit to unsigned-divide that value by 2 (denoted by the >> operator).
    If we have a dividend value of 100 (1100100), and we want to divide it by 5 (101), we start off by getting the difference in bit positions between them. Subtracting the number of bits from dividend (which is 7) by divisor (which is 3), gets us 4 bits. If we scale 1 bit up with 4 bits, as in 2 to the power of 4, it will become 16. 16 times 5 equals 80.
    We scale up the divisor by 16, making it 80. For every bit we have left, of this scaling (4 bits, 2 to the power of 4), if divisor is less or equal to dividend, turn the current scaling bit on in the quotient (starts off at 0) and subtract divisor from dividend (becoming the modulus).
    Then shift the scale to the right by one bit (dividing it by 2), and do the same thing to divisor. And repeat these steps as long as the scale is not 0.
     
    Let's do a test run:
    dividend = 100, divisor = 5, scale = 1 << 4 bits (to the left) (16), quotient = 0.
    divisor = (divisor << 4 bits (to the left)) = 80.
    For as long as scale is not 0:
    (
     Only if divisor is less or equal to dividend (true):
     (
     quotient = quotient + scale (becomes 16).
     dividend = dividend - divisor (100 - 80 = 20).
     )
     divisor = divisor >> 1 (becomes 40).
     scale = scale >> 1 (becomes 8).
    )
    For as long as scale is not 0:
    (
     Only if divisor (40) is less or equal to dividend (20) (false):
     (
     quotient = quotient + scale.
     dividend = dividend - divisor.
     )
     divisor = divisor >> 1 (becomes 20).
     scale = scale >> 1 (becomes 4).
    )
    For as long as scale is not 0:
    (
     Only if divisor (20) is less or equal to dividend (20) (true):
     (
     quotient = quotient + scale (becomes 20).
     dividend = dividend - divisor (20 - 20 = 0).
     )
     divisor = divisor >> 1 (becomes 20).
     scale = scale >> 1 (becomes 4).
    )
    For as long as scale is not 0:
    (
     Only if divisor (20) is less or equal to dividend (0) (false):
     (
     quotient = quotient + scale.
     dividend = dividend - divisor.
     )
     divisor = divisor >> 1 (becomes 10).
     scale = scale >> 1 (becomes 2).
    )
    For as long as scale is not 0:
    (
     Only if divisor (10) is less or equal to dividend (0) (false):
     (
     quotient = quotient + scale.
     dividend = dividend - divisor.
     )
     divisor = divisor >> 1 (becomes 5).
     scale = scale >> 1 (becomes 1).
    )
    For as long as scale is not 0:
    (
     Only if divisor (5) is less or equal to dividend (0) (false):
     (
     quotient = quotient + scale.
     dividend = dividend - divisor.
     )
     divisor = divisor >> 1 (becomes 2).
     scale = scale >> 1 (becomes 0).
    )
    scale is now 0. The division is completed, and quotient (20) is our result as well as modulus being dividend (0).
     
    Let's do another test run. This time we do 5555 / 5555:
    dividend = 5555, divisor = 5555, scale = 1 << 0 bits (to the left) (1), quotient = 0.
    divisor = (divisor << 0 bits (to the left)) = 5555.
    For as long as scale (1) is not 0:
    (
     Only if divisor is less or equal to dividend (true):
     (
     quotient = quotient + scale (becomes 1).
     dividend = dividend - divisor (5555 - 5555 = 0).
     )
     divisor = divisor >> 1 (becomes 2777).
     scale = scale >> 1 (becomes 0).
    )
    scale is now 0. The division is completed, and quotient (1) is our result as well as modulus being dividend (0).
     
    Let's do another test run. This time we do 256 (100000000)/ 33 (100001):
    First, we need the difference of bits between the top bits of dividend (9) and divisor (6): 9 - 3 = 3.
    dividend = 256, divisor = 33, scale = 1 << 3 bits (to the left) (8), quotient = 0.
    divisor = (divisor << 3 bits (to the left)) = 264.
    For as long as scale (8) is not 0:
    (
     Only if divisor (264) is less or equal to dividend (256) (false):
     (
     quotient = quotient + scale.
     dividend = dividend - divisor.
     )
     divisor = divisor >> 1 (becomes 132).
     scale = scale >> 1 (becomes 4).
    )
    For as long as scale is not 0:
    (
     Only if divisor (132) is less or equal to dividend (256) (true):
     (
     quotient = quotient + scale (becomes 4).
     dividend = dividend - divisor (256 - 132 = 124).
     )
     divisor = divisor >> 1 (becomes 66).
     scale = scale >> 1 (becomes 2).
    )
    For as long as scale is not 0:
    (
     Only if divisor (66 (1000010)) is less or equal to dividend (124) (true):
     (
     quotient = quotient + scale (becomes 6).
     dividend = dividend - divisor (124 - 66 = 58).
     )
     divisor = divisor >> 1 (becomes 33 (100001)).
     scale = scale >> 1 (becomes 1).
    )
    For as long as scale is not 0:
    (
     Only if divisor (33 (100001)) is less or equal to dividend (58) (true):
     (
     quotient = quotient + scale (becomes 7).
     dividend = dividend - divisor (58 - 33 = 25).
     )
     divisor = divisor >> 1 (becomes 16 (10000)).
     scale = scale >> 1 (becomes 0).
    )
    scale is now 0. The division is completed, and quotient (7) is our result as well as modulus being dividend (25).
    A simple check to see if this is correct: 33 * 7 + 25 should equal 256.
     
    A signed divide requires us to negate the resulting quotient if the divisor's sign bit was not equal to the dividend's sign bit, as well as the modulus being negated if dividend's sign bit was turned on. The division must be done on the absolute (positive) values of dividend and divisor as the test runs demonstrate.
     
     
    Why do we need the difference between the top bits of dividend and divisor? And why do we scale up the divisor with that number of bits? Sadly, I don't know.
     
    Division is one of the slowest operations. Only Square Root is slower. Therefore it is better to multiply with fractions (reciprocal of the value) when using floating point even if it yields worse precision. For integer math, bit shifting to the right to divide by a power-of-2 value is much much faster. However, CPUs are smart and can find those cases for you most of the time, so the speed is the same. Division and Modulo are always needed, and eventually you just need to use them when there is no other way.
     
    This is my 11,000 post on this forum!
  6. Splashee

    Binary Math ("The Wrapping Point")

    By Splashee,


    Binary Math
    In game development, maybe the most common way to time "events" is to use a delta time. The absolute time that is considered "now" minus the previous absolute time, gives you a delta time:
    You can then multiply this delta time with the events and physics of the game. This is very common but have a lot of problems that creep in later. One of those problems might appear out of nowhere, and is the wrapping point.
     
    Consider you have an absolute time of 56670001 milliseconds, and your old absolute time was 54999198. That gives a delta time of 1670803. This delta time is positive. Since you know time always moves forward, the delta time will always stay positive. So you expect that to always be the case. What if that somehow changes? How do you deal with it? Should you deal with it?
     
    Over many decades, milliseconds were stored as 32-bit binary values. If we do the math of converting the highest possible 32-bit value into the unit "days", we will get:
    That means, after 49.7 days, the milliseconds counter will overflow, and wrap around back to 0 again.
     
    That means, the absolute time that is considered "now", will be smaller than the previous absolute time, yielding in a negative delta time. All of a sudden, time is moving backwards. What that has as an effect depends on what the delta time is used for. But for that odd time stamp, that happens not that often, can cause real headache!
    So what? Just add a check:
    if (now < previous) delta = previous - now; else if (previous <= now) delta = now - previous; Does that solve the problem?
    Or what about this:
    delta = abs(now - previous); Using the absolute number, does that solve the problem?
     
     
    Binary Math has a way to solving the problem for us. It comes in the form of two's complement (read about it here: Binary Math (Subtraction and Negate)). Because negative values are just very large positive values, adding or subtracting such values will automatically overflow the numbers, auto wrapping them into a relative value for us.
    Take the example of an absolute time for "now" being 5, and a previous time being 4294967291 (which is -5 in 32-bit). We now have the problem that if we subtract 4294967291 from 5, we will get -4294967286 which is a negative value, and time doesn't move in the negative direction.
    But what if the value was wrapping around 4294967296? How can we test this? With modulo of course! Gotta love the modulo operator (not really, as we will get into later):
    As you might expect, you will get the result of -4294967286, the same as before. But sadly, using the modulo operator on a negative value to begin with will not give the result we need.
     
    Because 32-bit values can only store 4294967296 unique numbers, -4294967286 is actually represented as 10. And if you just do the math 5 - (-5), you will get 10! 10 is positive, and time is moving forward again, even if the absolute time of "now" had wrapped over from 4294967291 to 5 with 10 units. Overflow just works!
    So the correct code would still just be be (no need for checks):
     
    delta = now - previous;  
     
    But there is a reason why I bring this up. We still have the problem of modulo. If computers just work, but modulo doesn't, then we do have a problem.
    The modulus operator, most commonly done with the percentage sign in C derived languages, is the integer remainder of a division:
    int dividend = 55; int divisor = 9; int quotient = dividend / divisor; // quotient == 6 int remainder = dividend % divisor; // remainder == 1  
     
    Modulo is mostly used to wrap random numbers, and for cryptography (usually with prime numbers), and we cannot live without that in our daily lives!
     
    Modulo is defined as x - y * floor( x / y ) for any number. Somewhat... I wouldn't like to check if that is correct.
     
    There is a problem, and I can easiest describe it with an analog clock of 60 minutes (having at least a minutes hand). If you have a time in minutes, any time, which will be a positive number, you can find which minute the minutes hand will be at, on that clock face. Since the clock wraps around every 60 minutes, the math is:
     
     
    If we have the minutes of 16571886, then the minutes hand will be on minute 6.
    We know that, if we subtract 7 from 16571886, the minutes hand will be on minute 59. And that is exactly true:

    It works!
     
    Now try this one. You are on minutes 59, and you subtract 61 minutes. Try the math now. You know the result should be 58. Because if you move 60 minutes, you will on 59 again, and one more minute backwards ends you on 58. However, modulo cannot handle this!
    Remember the value 16571879 above? It was 59 on the clock, so what if we subtract 61 from that?
     
    So, that works. So there is a big problem. And that's why it is very difficult to do these wrapping point stuff that the computers do with binary numbers, with so called "real math". So how do we solve these problems with "real math" then? I am still working on a solution to this day, but it is much more complicated than that, when you try to do the above delta time, when using modulo on both absolute times in a similar way as the computer overflows binary numbers, automatically for you.
  7. Splashee
    Before we start with multiplication, it is important to understand that basically every CPU out there has a built in multiplication instruction. Why is this important? Well, because when I started doing research about Binary Math for my blog, I had very limited understanding of how multiplication and division worked, and while division is not supported by low end CPUs, multiplication is. And I can assure you that I cannot disassemble a CPU to figure out how multiplication is done!
    The C and C++ standard requires the operations of addition, subtraction, multiplication, division, and modulo. If the CPU cannot provide any of them, they must be emulated and provided by the C/C++ compiler. That’s exactly what the compiler does for the CPUs that don’t support division. So after realizing how division is being emulated, I could figure out one way of doing multiplication! There are many ways of doing multiplication, and my take on it might not be the best. I am still proud I was able to work out a solution that gave the same results as the multiplication made by the CPU!


     
    Knowing that multiplication can be done in a slow way, by just addition in a loop, there are still a few problems we need to concern ourselves with. The first one is obvious:



    Make the loop count as small as possible. Loops are kind of slow on computers, because after a certain number of looped instructions, there must be a way of breaking out of the loop, and such a test requires the CPU to flush the cache. We must loop, so we must try to make the number of times (loop count) as small as possible. If we were to multiply 5 by 1000, then Adding 1000, five times is way faster than adding 5, athousand times. We need to find the factor that is smaller than the other factor. And we need to do this in Binary Math!


     
    The second one might not be as obvious:

    Deal with one or two factor(s) being negative number(s). As been seen in my previous blog about subtraction, negative numbers have their own rules to them. Adding a negative number is subtraction. How does that affect our multiplication product? Are there any specific rules that force us to not use negative numbers in the first place?


     
    Dealing with negative numbers:

    Learning from how division is dealt with, I simply know that it is possible, and best, to make the factors positive before calculating the product.
    If one factor is negative, and the other factor is positive, the product will be negative. If both factors are negative, the product will be positive. Else, the product is positive.


     
    First we must check if any or both factors are negative:


     
    If the most significant bit of Factor 1 is 1, it is a negative number, so make it positive by doing a two’s complement operation on the number, and finally set a Flag to 1 to indicate a negative Product. Else, keep the Flag 0 to indicate a positive Product.


     
    If the most significant bit of Factor 2 is 1, it is a negative number, so make it positive by doing a two’s complement operation on the number, and then do a bitwise NOT on the Flag to make it 1 if it was 0, or 0 if it was 1. The sign of the Product depends on the result of this Flag.


     

     
    Dealing with factor size:

    After we have only positive factors, we need to check their size. If either factor is 0, the product will be 0 (we should have done this before making the factors positive).



    So the main problem is to check which factor is less than the other factor, as we want the loop count to be as small as possible. The loop count is the number of times we need to add the other factor with itself to get the product.

    Factor 1 is less than Factor 2 if the difference between Factor 1 and Factor 2 is negative, else the difference is positive (or zero). Let’s say Factor 1 is 50 (110010) and Factor 2 is 49 (110001), and we are testing for Factor 1 being less than Factor 2:


     
    First, prepare the subtraction by doing a two’s complement on Factor 2 to make it negative…


     
    Invert each bit, and then add 1. This is explained in my previous blog entry about subtraction:


     
    110001.


     
    Bitwise NOT (invert bits):

    001110.


     
    Something went wrong here! Why do we still have a positive value? The most significant bit is 0 here, and it must be 1 to be a negative number. We have forgotten that in order to have negative numbers, we must have space for negative numbers. The highest number we can represent with 6 bits is 63, and half of that will be negative numbers if we treat the most significant bit as negative numbers. You can see that we already started out as a negative number before we started inverting the bits. I did this error on purpose, so that we are forced to understand negative numbers and not just how to calculate them! We need to extend the number of bits, so we can have negative numbers in the range of our example. This will work for now: Factor 1 is 50 (0110010) and Factor 2 is 49 (0110001). We only placed a zero in front of the binary numbers to make it work.
    Let’s do the two’s complement on Factor 2 again:


     
    0110001 (49).


     
    Bitwise NOT (invert bits):


     
    1001110 (-50).


     
    And add 1:


     
    1001111 (-49).


     
    We have successfully done two’s complement, which made 49 negative (-49). Now we can add Factor 2 to Factor 1, and if the result is negative, Factor 1 is less than Factor 2:


     
    x1111100 ________ 0110010 +1001111 ________ 0000001
     
    (Note: We are only allowing for 7 digits, meaning the last carry stated here as an “x” is discarded! The number has passed the wrapping point, wrapped around and become a positive number, as a default part of Binary Subtraction. If this was not subtraction, the addition overflowed and the carry “x” tells us of that overflow!)


     
    The result is positive, if the most significant bit is 0, which it is! That means Factor 2 is less or equal to Factor 1. This is a deliberate choice of mine to show what we need to do, to swap the factors around.


     
    Swapping factors:

    When we only deal with two binary numbers, they can be swapped (exchanging place with each other) by stepping through 3 Logical XOR operations. As I stated in my previous blog, Logical XOR is outside the scope of this blog (really, I tried to explain it, but it was more than I have currently written, so no).
    So we could just say, Factor 1 is now Factor 2, while Factor 2 is now Factor 1, and problem solved.


     
    But for the sake of clarity, I’ll show the step with assigning values as well:

    Assign Factor 2 (49) to Temporary Factor (?).

    Assign Factor 1 (50) to Factor 2 (49).
    Assign Temporary Factor (49) to Factor 1 (50).
    Result is Factor 1 (49) and Factor 2 (50), as they are now swapped!



    The Temporary Factor is only used to remember Factor 2, as it is being overwritten by Factor 1 before it can be written to Factor 1.


     

     


    Looping though a factor:
    As I stated before, multiplication is done by looping through the smaller factor, and adding the larger factor.
    Well, it can be done that way, but binary works with power of 2 values. Instead of looping 49 times, we can choose to only loop 6 times instead. Why 6? Count the number of digits we must loop through, and it is made clear that the highest bit (furthest to the left hand side) that is 1 in the number 49 is located in the 6th digit: 0000000000000110001.
    I added a lot of unnecessary zeros to show that the larger the number is, the bigger the loop count can become, but it is still far away from being as much as 49!


    Adding to the product:
    So we know we have to loop 6 times, but we don’t know what we need to add during each loop count. We are currently dealing with digit positions now, and their value, how much they are worth. We have already covered this in my first blog, about how to do addition and convert binary numbers to decimal numbers.
    For each digit position, starting from the rightmost digit, the value is worth twice as much as the previous digit’s value to the right. Being at the very right, the value is worth 1. Meaning, the value of the digit to the left of that digit is worth 1 + 1 = 2. The next digit to the left is worth 2 + 2 = 4. Next is worth 4 + 4 = 8, etc.
    The simplest form of multiplication is just to shift the digit from one position to the next, in the direction right to left. If you have the number 0001 which is worth 1, shifting that 1 bit two digits to the left, will make it worth 4 times as much: 0100 (4)!
    Guess what, it works on any number! Imagine you have the number 5 (000101), and you shift it (all the bits) two digits to the left, will make it worth 4 times as much: 20 (010100)!

    This is multiplication with a number that is a power of 2. However, it is not multiplication! We never multiplied anything. We just moved bits, from one digit to another digit, so called Bit Shifting. It is one of those bitwise operations, like Bitwise NOT. The name is actually Bitwise Shift Left. Or in short, Bitwise SHL.
    The opposite of Bitwise SHL is Bitwise SHR (Bitwise Shift Right), and you would think it does the opposite as well, divide by a number that is a power of 2? You would be so close if you guessed YES! It is almost true, but it doesn’t work with negative numbers. And Binary Division doesn’t use it at all, as division also tracks the remainder. We’ll discuss Binary Division in my next blog entry.


     
    So, we can multiply any binary number, including negative binary numbers by a number that is a power of 2, such as 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2084, 4096, 8192, etc. All we need to do is shift the bits to the left by as many steps required to reach the digit’s value.
    But what if we need to multiple by a number that isn’t a power of 2?
    Let’s say we want to multiply some number with the number 6. The number 6 is the sum of two power of 2 numbers:



    4 and 2.


     
    So if we have the number 1 (0001), and we want to multiply it with something to make it 4 (0100), all we needed to do was Bitwise SHL with 2. And the same goes if we have the number 1 (0001), and we want to multiply it with something to make it 2 (0010), all we have to do was Bitwise SHL with 1. If we then add the result of those shifts, we will get the number 6 (0110).
    The important thing here is that we started out with the number 1 acting as the first factor. The two shift operations Bitwise SHL 2 and Bitwise SHL 1 acting as the second factor. And the sum of those shifts on the number is the product of the multiplication!

    We did 1 * 6 = 6.


     
    If we were to change 1 (first factor) into any other number, we would still multiply with 6 because of the two shift operations acting as the second factor. The question is: How do we find out how many shift operations we need? For 6 we needed two shift operations.
    We have a partial answer in the loop count. The loop count for our factor 49 is 6, because that is the maximum digits we have to go through, to make up 49 inbinary. The other part of the answer comes from whether the digit is 1 or 0.

     

     
    Adding shifted binary numbers to make the product:

    So we start out with the Product being 0. For every loop in the loop count, we want to add a shifted factor. The question is, how much do we shift Factor 2 (50) before we add it to the Product? Well, every digit’s position in Factor 1 holds the answer, if the digit is 1. We need to shift Factor 2 (50) with the number of digit-positions where that 1 is located at, minus 1, because the first digit’s position shouldn’t be shifted (multiplied by 1, itself). Then, we add the result of that shift to the Product, and we do this until we have done 6 loops, or should I say 6 digits of Factor 1. And yes, if a digit from Factor 1 is 0, we do not shift and add anything!

     
     

     
    Time for the looped action:

    We have a loop count of 6, knowing that this is the maximum digits to process in Factor 1. We decide to do the digits right to left, even if it is possible to do them in the opposite direction. We start with the Product set to 0, and to help understand better, we do the examples where we shouldn’t, for clarity since shifting digits might be a new thing to you:


     
    -Loop1 out of 6:
    Check the 1st digit in Factor 1 (0110001) if that digit is 1, else go to the next loop…
    Shift Factor 2 with the number that represents the 1st digit’s position, minus 1. This means we will shift by the number 0, which isn’t a shift at all!

    Add to the Product (0), Factor 2 (0110010) Bitwise SHL with 0, which is still (0110010).

    The Product is now 50  (0110010). Go to the next loop…


     
    -Loop2 out of 6:
    Check the 2nd digit in Factor 1 (0110001) if that digit is 1, else go to the next loop…
    Shift Factor 2 with the number that represents the 2nd digit’s position, minus 1. This means we will shift by the number 1:

    Add to the Product (50), Factor 2 (0110010) Bitwise SHL with 1, which is (01100100).

    Product is now 150  (010010110). Go to the next loop…


     
    -Loop3 out of 6:
    Check the 3rd digit in Factor 1 (0110001) if that digit is 1, else go to the next loop…
    Shift Factor 2 with the number that represents the 3rd digit’s position, minus 1. This means we will shift by the number 2:

    Add to the Product (150), Factor 2 (0110010) Bitwise SHL with 2, which is (011001000).

    The Product is now 350  (0101011110). Go to the next loop…


     
    -Loop4 out of 6:
    Check the 4th digit in Factor 1 (0110001) if that digit is 1, else go to the next loop…
    Shift Factor 2 with the number that represents the 4th digit’s position, minus 1. This means we will shift by the number 3:

    Add to the Product (350), Factor 2 (0110010) Bitwise SHL with 3, which is (0110010000).

    The Product is now 750  (01011101110). Go to the next loop…



     
    -Loop5 out of 6:
    Check the 5th digit in Factor 1 (0110001) if that digit is 1, else go to the next loop…
    Shift Factor 2 with the number that represents the 5th digit’s position, minus 1. This means we will shift by the number 4:


    Add to the Product (50) <Note: We arrive here from Loop 1>, Factor 2 (0110010) Bitwise SHL with 4, which is (01100100000).

    The Product is now 850  (01101010010). Go to the next loop…

     
    -Loop6 out of 6:
    Check the 6th digit in Factor 1 (0110001) if that digit is 1, else go to the next loop…
    Shift Factor 2 with the number that represents the 6th digit’s position, minus 1. This means we will shift by the number 5:


    Add to the Product (850), Factor 2 (0110010) Bitwise SHL with 5, which is (011001000000).

    The Product is now 2450  (0100110010010). And the loop is completed!


     

     
    We did 50 * 49 = 2450.


     

     
    But, don’t forget to check the Flag at the end! If the Flag was set to 1, it means the Product should be negative, because one of the factors was a negative number. A two’s complement operation on the Product will make it negative.


     
    And that is Binary Multiplication!

  8. Splashee
    This is a follow up to the previous blog entry (read it first to understand Binary numbers):
     
     
    Subtracting two binary numbers is as easy as adding two binary numbers. In fact, it is the same.
    Computers deal with bits, and the number of bits are limited. The smallest number of bits that the computer can access is 8 bits, called a "BYTE" (a wordplay of "by eight"). 8 bits can contain 256 different bit pattern combinations, and that gives us the total numbers we can count using binary math with 8 bits. The origin of 8 bits is actually tied to characters, in order to store letters (to emulate old type writers).
    We are however still bound to 256 different bit patterns, when we want to include negative numbers.

    Binary numbers wrap around. The bit patterns keep repeating even when we run out of bits. That means that if we are on the number 255 and we add 1, we will end up on 0. And if we are on 0 and subtract 1, we will end up on 255 again. Note that 255 in this case is positive! Also note that we subtract decimal numbers here, not binary numbers.
    With a limited number of bits available, it is easier for the computer to simply ignore the subtraction operation for binary numbers as it is the same result to add a negative number as it is to subtract a positive number.
     
    An example:
    9 - 5 = 4 (subtraction)
    9 + -5 = 4 (addition)
     
    Without subtraction, the computer doesn't need to "borrow" digits. Instead, digits can be "carried" using addition instead. One system to deal with two operations, is simply smarter. Subtraction can then be disguised behind the scenes as addition with negative numbers.
     
    But we still need to know what a negative number is. We need to have a way to identify a negative number from a positive number. And we need negative numbers to be lower than positive numbers, so that we can "move backwards" in the bit patterns that the binary numbers represent.
    Remember how I told you earlier that binary numbers wrap around? It is the wrap around that makes the magic possible, and allows us to do math in the reverse direction. By adding a large number to our current number, it will most likely wrap around. Adding for example 256 to any number in a BYTE would equal the same number before the addition took place, since a BYTE can only store 256 unique bit patterns. The previous statement has a huge error in it, and that is, we cannot add 256 since the largest number we can represent in a BYTE is 255. If we go by BYTE size numbers, that is. I said 256 unique bit patterns, and if you think about it, one of them is 0. Since binary numbers wrap around, adding 1 to 255 should in fact give us 256, however it gives 0. And I also said if we could add 256 to any number, that would give us the same number, and adding 0 to any number would do the same thing. So 256 and 0 is the same number in the world of wrapping.
    Wrapping around can be a serious headache. But it has the solution to our problem:
    If we can only represent any number between (and including) 0 to 255. Then adding 255 to any number of our choosing, will wrap around the result to our number minus 1. We have a way to do subtraction by 1.
    So what is 255 then? The numbers wrap around so if we subtract 1 from 0, we will end on 255. That means, 255 must be equal to -1. Let's just stop here, and say that the value 255 can be both 255 and -1. Because that is the truth. Wrapping is a pain to understand, and we need to see it to believe it. So let's get down to the basics. In a world of BYTEs, where nothing can be smaller, binary numbers can be smaller, and they can wrap around at other values than 256, such as 128, 64, 32, 16, 8, and 2.
     
    Let's choose the wrap around to be 16. By doing that, we can in the most easiest way see how wrapping works including representing both positive numbers and negative numbers.
    We draw a circle, like an analog clock (read it clockwise). It has bars to represent each number, 16 in total. In the outer part of the circle, we name each bar with a positive decimal number, as well as the binary number limited to 4 digits (4 bits). The inner part of the circle has the positive and negative decimal numbers, if we chose to represent the binary numbers as signed numbers:

    At the top of the outer part of the circle, the bar is named 0. It is the wrapping point, as the numbers wrap around there. 16 and 0 are the same number, only we cannot represent 16 in a binary number with only 4 digits. Standing on 15, and adding (moving clockwise by) 1, will end up on 0. And standing on 0, and subtracting (moving counter clockwise by) 1, will end up on 15. You can also see that 15 is represented as -1 by reading the inner part of the circle.
    Another thing to notice is that half of the circle seems to be on the negative number side, and the other half on the positive number side. There are actually the exact same number of negative numbers as there are positive numbers, if you count 0 as a positive number.
     
    Let's dive deeper into this half circle. Look at the bit patterns of the blue numbers, the binary numbers limited to 4 digits. Notice the leftmost digit is 0 if the number is positive? And it is 1 if it is negative? This digit, or bit, has a name: "Most Significant Bit". It is the minus sign, telling us that the number is a negative number. If we want to play with negative numbers, then we can simply make a number negative by turning the leftmost digit from 0 to 1, making it act as a minus sign. That will tell us that the number is negative, however, it will not make the current number into its negative form. Here is an example, if you have the number 3, and want to make it negative, turning on the leftmost bit will yield the number -5. You can see it if you look at the blue binary numbers in the circle! We cannot negate a number without a specific formula.
     
    If we want -3 from 3, or 3 from -3, a negate operation, we cannot just add a number. We need to do an operation known as two's complement.
    Two's complement works on any binary number, no matter how many digits there are to represent the number. We don't need to think about the wrapping point. We only need addition, and an operation known as bitwise NOT. (In computer logic, both addition and bitwise NOT are done using a bitwise XOR on finite bit numbers. XOR is outside the scope of this blog entry!)
    If you have a binary number, you can easily do a bitwise NOT by stepping through each digit, and swap the digit from either 0 to 1, or 1 to 0. All the bits in the binary number will become inverted. If you invert something twice, it becomes the same value again. Let's try it on a really long and unknown binary number:

    10010100100101010101001010101101111110001

    Inverted using bitwise NOT:

    01101011011010101010110101010010000001110
    And invert it again using bitwise NOT will yield the original number:
    10010100100101010101001010101101111110001
     
    So, if you have 3, and you want -3. First represent 3 as its binary number:

    0011
    Invert each bit (using bitwise NOT):
    1100
    Now add 1, and you will end up on -3:
    1101
    Confirm with the circle above!
     
     
    So, we should be able to do the same with -3, to get 3. Let's do the same two's complement to prove that it works:
    1101
    Invert each bit (using bitwise NOT):
    0010
    Now add 1, and you will end up on 3:
    0011
    Confirm with the circle above!
     
    Yes, this is done with 4 digits, so that we can draw a circle with only 16 steps, and get a nice amount of positive and negative numbers, in order to learn wrapping and two's complement.
    But how do we subtract a number then?
     
    This is where you have to read the first blog entry (see the top for a link), for how you do addition with binary numbers. All you need to do is add a number that is negative, to subtract. It is that simple!
    And how do you get a negative number? With two's complement.
     
     
     
     
    This is the end of this blog, however, as a game programmer, I am using wrapping all the time...
     
     
    Next up in the blog, we have Binary Multiply... (See you next time!)
  9. Splashee
    When programming games for a computer, either it being a game console, or a PC, it is very handy to understand how binary numbers work. The Ones (1) and Zeroes (0) that control the computer's brain, the CPU, as well as the bits stored in memory or on physical media.
    While bits are patterns of Ones and Zeroes, and can represent anything such a text, or graphics, it is also used to store and calculate numbers. These numbers are stored in binary form, and the CPU knows how to read them. We humans can read them too:
     
    11001011011 is binary for the number 1627. The colors I have chosen is blue for binary, and purple for decimal number (the numbers we humans count with). Reading binary is easy! We have to step though each digit at a time, starting right and move towards left until all bits have been processed. For each step (digit position) we take, we must add a number to our final result. The final result will be in decimal form, and starts at 0 when we begin translating:

    The first digit (to the very right) in the binary number is worth exactly 1 decimal. If that digit is 1, then we must add 1 to the final result. If it is 0, then we will skip it. Then we move to the next digit to the left of the previous one.
    The second digit in the binary number is worth exactly (1 + 1) decimal (which is 2 decimal). If that digit is 1, then we must add 2 to the final result. If it is 0, then we will skip it. Then we move to the next digit to the left of the previous one.
    The third digit in the binary number is worth exactly (2 + 2) decimal (which is 4 decimal). If that digit is 1, then we must add 4 to the final result. If it is 0, then we will skip it. Then we move to the next digit to the left of the previous one.
    The fourth digit in the binary number is worth exactly (4 + 4) decimal (which is 8 decimal). If that digit is 1, then we must add 8 to the final result. If it is 0, then we will skip it. Then we move to the next digit to the left of the previous one.

    Have you notice a pattern? Each digit to the left of the current one's position is worth 2 times as much! That's because binary is base-2. In our decimal system, which is base-10, each digit to the left is worth 10 times that of the current digit's position.
     
    So to read the value 11001011011, we have to go through each digit's position and add how much they are worth, but only if the digit is 1, and not when it is 0! We begin with the final result being 0:
    First digit is 1, so the result is 1...
    Second digit is 1, so 2 is added to the result making the result total 3 so far...
    Third digit is 0, so skip (else you would have added 4 to the result)...
    Fourth digit is 1, so 8 is added to the result making the result total 11 so far...
    Fifth digit is 1, so 16 is added to the result making the result total 27 so far...
    And next digit is 0 so skip (else you would have added 32 to the result)...
    And next digit is 1, so add 64 to the result making the total 91 so far...
    And next digit is 0, so skip (else + 128)...
    And next digit is 0, so skip (else + 256)...
    And next digit is 1, so add 512 to the result, total 603...
    And the last digit is 1, so add 1024, and the final total result is............................... 1627.
     
    Adding two binary numbers together is done in using the same rules as adding decimal numbers, (by hand) easiest done with the columnar addition approach. Remember that carrying over to the next digit's column is done when an overflow occurs, such as 1 + 1 or (1 carry) + 1 + 1, just similar to how decimal addition works, 9 + 1 or (1 carry, which is worth 10) + 9 + 1. So if you didn't get that last part, it probably doesn't matter as you might be using a different format. The rules of the math is the same though!
    Let's do an example. Let's add the number 2 and 1 together, so that the sum is 3. That is easy since you don't need columnar addition... However, in binary, those numbers are 10 and 1 and 11 respectively. So we should/can use columnar addition:
    10 + 1 ___ 11 First column, 0 and 1 is added to make 1. In the second column, 1 is added to nothing, or 0 if you may, and the final sum is 11.
     
    Let's do another example:
    101101 + 10010 _______ 111111 Pretty straight forward. But the numbers here are quite interesting. Because we are using binary instead of decimal, we don't need to use any carry! But the binary number 101101 is the decimal number 45, the binary value 10010 is the decimal number 18, and the binary number 111111 is the decimal number 63, a carry is required when doing this calculation in decimal form:
    (1) <- Carry __ 45 +18 ___ 63  
    Carrying is done in the same way with binary numbers:
    (1) __ 1 + 1 ___ 10 First column, 1 and 1 is added to make 10, but since that number can be stored as a single digit, the digit 1 is carried over to the next column to be added next. In the second column, 1 (the carry) is added to nothing, or 0 if you may, and the final sum is 10.
    Of course, there is the case where we must add 1 and 1, as well as a carry (1), and the sum would then be 11. Then 1 is stored in the column, and the other 1 is carried over to the next:
    (11) ____ 11 + 11 ____ 110  
    And that concludes addition of binary numbers. Next up is subtraction, however, it is not as you may think. See you next time!
  10. Splashee
    As a request from a member of this forum, that shall go unnamed, I have been assign to teach how to compose music. So why not create a blog entry for that?
    I am a music composer, whatever that means? It means I am an artist, but with music instead of art, because those are kinda similar, but not.
    If you are a music composer yourself, or someone who can play music from reading sheet music, you won't be impressed. If you have never before heard music, you might be a little impressed, but most likely, you won't be.

    So where do I start? Where does the music come from? Usually, nothing comes from the void, but is rather pieces of other things I have heard under a very long time, that somehow got merged together and became something new (like when you dream). Usually it is a melody stuck in my head, that I try (emphasis on try) to remember so that I can do something with it in the future. If you can whistle, then you pretty much know what a melody is, because it is that part you usually sing to (when it is a song), or whistle.
    Let's start with a simple melody (an annoying one):

    So where do we go from here? Well, usually we want the roots of the chords, so we will know where the melody is heading (or staying at, or whatever). That will lead to creating the bass line. However, for the fun of it, I am waiting with the roots, and giving you the harmony instead. That is because the harmony has its own roots, kinda, to be confusing. When composing music, try to be as confusing as possible to the ear. But also, when we add the bass, we want it to have its own melody (eh, confusing, that's what we are aiming for!).
    So here are the harmonies:
    If you can count to 4 within the first Major 7th chord, then, be prepared when the bass has been added, as 2 of those beats will be its own chord, and the other 2 will be a sus chord. That stands for suspended. There are many kinds of suspended chords, and some of them are nameless. While many of you know of the sus2 and sus4 chords (which are blah), most pop songs uses the bass + 1 for the suspended effect, and we will too! By playing a Major chord and move the bass from the root by + 1 (not semitones, but on the major scale), the chord's harmony changes into a Dominant sus. You have the Dominant 7th and 9th as part of the previous chord, but the bass which must be the root forces the 9th and the broken 11th into a sus chord, which melts most people's ears (including mine). Any 11th chord are broken, and shouldn't be used.
    So here are the chords you here in the harmony, in the order you hear them (I only care about the harmony, not the base chord because this music is transposed by a few seminotes):
    Maj7
    Maj7
    Maj7
    Major
    Min7#5
    Min7
    Major
    Dominant9sus
    sus4
    sus4
    Major6
    Min7#5
    Min7
    Major9
    Major
    Dominant13add2
    I could go on about these chords forever. Though, even if they have a meaning by themselves, they will not mean the same when we add the bass to the mix.

    Time for the bass. Well, just have a listen:

    So with the highest part of the music being defined to be the melody, and the lowest part of the music being the bass, let's listen to them together (the rhythm between them might be the thing you have to be born with to be a truly good composer. Sadly, I am not):

    Now, to combine the bass and the harmony, to create those sus chords and complex ear bleeding stuff. There is one thing I haven't talked about, and it is the horrible Major 6th chords in there. The melody might force this to be music in mostly Major 6th, but any Major 6th chords should be banned because they are manipulative. Thankfully I only have a split second of the music actually playing the Major 6th. I could make a whole blog post just about why Major 6th is evil, but for now, let's concentrate on this d*mn thing:
    And to complete the different variations, here is the melody and harmony together (the music is pretty much completed when the drums kicks in):
     
     
    And to finalize this thing, the final music (all combined, good riddance!):

    Now if I managed to be a good teacher, all of you will compose great music in the future. But from experience, I am not a good teacher. Also, I will take questions if there are any?
×
×
  • Create New...