Binary and adders

Ankush

Nov 21, 2015 22:28

Hello

Ixrec

so I guess the place to start would be

ratchet freak

Arithmetic logic unit

An arithmetic logic unit (ALU) is a digital electronic circuit that performs arithmetic and bitwise logical operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on floating point numbers. An ALU is a fundamental building block of many types of computing circuits, including the central processing unit (CPU) of computers, FPUs, and graphics processing units (GPUs). A single CPU, FPU or GPU may contain multiple ALUs. The inputs to an ALU are the data to be operated on, called operands, and a code indicating the operation to be performed; the ALU...

Ixrec

do "logic gates" make sense to you? (assuming you read that far in the How do computers work? post)

that too yeah

ratchet freak

the ALU is the "magic component" that make math work

user55340

Adder (electronics)

In electronics, an adder or summer is a digital logic circuit that performs addition of numbers. In many computers and other kinds of processors, adders are used not only in the arithmetic logic units, but also in other parts of the processor, where they are used to calculate addresses, table indices, increment and decrement operators, and similar operations. Although adders can be constructed for many numerical representations, such as binary-coded decimal or excess-3, the most common adders operate on binary numbers. In cases where two's complement or ones' complement is being used to represent...

ratchet freak

Nov 21, 2015 22:30

and is comprised of ^

user55340

(and the hyper physics item: hyperphysics.phy-astr.gsu.edu/hbase/electronic/fulladd.html )

user55340

user55340

Given that truth table, get the proper set of gates.

user55340

Ixrec

I guess I'll be quiet for a minute while he processes everything we just linked

Ankush

Nov 21, 2015 22:32

hahaha thanks

ratchet freak

subtracting means some bit magic by negating the second number before adding

Ixrec

one step at a time! lol

user55340

@Ixrec one bit at a time.

Ankush

So then subtraction works by adding negative numbers? like instead of doing 10 -5 a computer would do 10 + (-5)?

ratchet freak

yeah

Ixrec

Nov 21, 2015 22:35

arguably that's what we do

user55340

Yep. Representing the negative number properly is a bit confusing at first though.

Ixrec

the proper answer to that part of the question is "two's compliment arithmetic", which is kinda magic

and that's a whole different subject from "how does a computer do 1 + 1 = 2?"

ratchet freak

and the representation (called 2's complement) lets you do that but doing a not for each bit and adding 1

user55340

Two's complement

Two's complement is a mathematical operation on binary numbers, as well as a binary signed number representation based on this operation. Its wide use in computing makes it the most important example of a radix complement. The two's complement of an N-bit number is defined as the complement with respect to 2N; in other words, it is the result of subtracting the number from 2N, which in binary is one followed by N zeroes. This is also equivalent to taking the ones' complement and then adding one, since the sum of a number and its ones' complement is all 1 bits. The two's complement of a number behaves...

Ixrec

I guess we're really hammering home the "you need a textbook" thing

user55340

Nov 21, 2015 22:36

01 + 01 = 10 --- thats all the adder thing above.

Ankush

Hahahha yeah, I think that would be a ton of help!

user55340

If you have an adder looking like that.

user55340

You can link them together:

user55340

Ixrec

Nov 21, 2015 22:37

to be clear, an "adder" is a particular circuit built from logic gates

these are all just circuits with wires going in and other wires going out

ratchet freak

and if you put a NOT gate on the B input and feed a 1 into C0 you can do A-B

Ankush

Wow well that seems concept is a lot more clear now

ratchet freak

of course that's just adding

Ankush

So then when dealing with addition or subtraction the computer basically uses the same "carry over" thing we are taught in school, but instead of using numbers from 1 - 9 it uses 0 & 1?

ratchet freak

multiplying and dividing is more complicated

Ixrec

Nov 21, 2015 22:40

it's using binary or base 2 numbers, yes

user55340

Yep. Just 0s and 1s

ratchet freak

@Ankush exactly

Ixrec

so if the inputs are 7 and 2, in binary that would be 0111 and 0010

which turns into 1001, or 9

Ankush

And hears me thinking a 15 year old could never grasp this :) Stack-exchange truly is my haven!

Ixrec

MichaelT's picture above shows a 4-bit adder, the A0-A3 wires correspond to the "0111" input, the B0-B3 wires correspond to "0010", and the S0-S3 wires correspond to the "1001" sum

@Ankush glad we could help

user55340

Nov 21, 2015 22:43

inst.eecs.berkeley.edu/~ee100/su07/handouts/…

Ixrec

of course to get a functional CPU out of this you have to add a clock signal, registers, an instruction pointer, lots of opcodes, a memory bus for loading and storying, and so on

user55340

That one starts out with binary, and finishes up with the adder.

user55340

Amusingly, its even got the same images.

Ixrec

and there's the magic of the two's compliment format for integers, and the IEEE 754 format for floating point numbers

ratchet freak

@MichaelT what a coincidence...

user55340

Nov 21, 2015 22:45

@ratchetfreak I grabbed mine from Wikipedia.

ratchet freak

so one is pulled from the other...

Ixrec

and as you've probably noticed, these circuits can only add numbers within a certain range

for that and many other reasons they're never a perfect match to what we think of as numbers

Ankush

Does that range depeend on the bit of the platform (16-bit, 32-bit, 64-bit etc.)?

user55340

Wikipedia is 2006, credited as "own work" by user cburnett. The pdf is 2007 with a number of refs to the wiki article.

Ixrec

it does

ratchet freak

Nov 21, 2015 22:47

good guess

Ixrec

typically a CPU's "word size" tells you the size of its registers and its adders and so on

I believe these days most of them use 64 bit words?

user55340

Whee: Javascript making computer slow! visual6502.org/JSSim

Ixrec

and in a programming language like C, there are multiple integer types corresponding to different sizes

how many bits each size represents does vary from platform to platform

ratchet freak

though there are constraints

Ixrec

@Ankush it gets weirder with floating point, since you can represent numbers like 1/2 in binary, but you can't perfectly represent 1/3 or 1/10 in binary

so rounding error is a constant concern

ratchet freak

Nov 21, 2015 22:52

you can only represent numbers with a power of 2 in the numerator

and a limit number of precision in the denumerator

it's easiest to thing of floating point as scientific notation

Ixrec

let's try not to get into subnormals

Ankush

If you had say 128-bits to work with, would you then have more presission and be able to represent values like 1/3?

Ixrec

1/3 and 1/10 are impossible to represent perfectly in any binary floating point value, it doesn't matter how many digits you have

more digits/bits will reduce the rounding error, but you can't eliminate it

note that 1/3 is also impossible to represent perfectly in decimal floating point (that's the familiar fact that 0.333333... goes on indefinitely)

user55340

99

A: Are there numbers that are not representable in base 10 but can be represented in base 2?

Here's the key to your quandary: 10 is the product of 2 and 5. You can represent any number exactly in base 10 decimals that is k * 1/2n * 1/5m where k, n and m are integers. Alternatively phrased - if the number n in 1/n contains a factor that is not part of the factors of the base, the number...

Ixrec

it is possible to write software that can do "arbitrary-precision arithmetic", but that revolves around them implementing every operation in software so they can do things like allocate more memory if the number gets too big or switch between several different number formats

user55340

Nov 21, 2015 22:58

Rational data type

Some programming languages provide a built-in (primitive) rational data type to represent rational numbers like 1/3 and -11/17 without rounding, and to do arithmetic on them. Examples are the ratio type of Common Lisp, and analogous types provided by most languages for algebraic computation, such as Mathematica and Maple. Many languages that do not have a built-in rational type still provide it as a library-defined type. == Representation == A variable or value of that type is usually represented as a fraction m/n where m and n are two integer numbers, either with a fixed or arbitrary precision...

Ixrec

so usually that's reserved for math-focused languages like MATLAB, and more general-purpose languages like C will stick to the typical hardware numbers

user55340

tryclj.com

user55340

> (/ 1 3)
1/3

Ixrec

and of course those languages can still run out of memory

user55340

@Ixrec should have seen me having fun with some project euler problems in Clojure where I was getting 1000 digit numerator and divisors)

user55340

Nov 21, 2015 23:00

projecteuler.net/problem=71

user55340

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

user55340

(so it wasn't 1000, it was 1,000,000)... I was just trying to have some fun... so I came up with all the numbers for n = 2, then n = 3, n = 4, n = 5 ... and iterated the numerator and stuck them in a set.

user55340

The JVM was not happy with me.

user55340

(aside, could I get a reject on this suggested edit: programmers.stackexchange.com/review/suggested-edits/124445 )

Ixrec

I'll stop there until we get asked another question

The Whiteboard

Participants