I tought myself how to read binary #361

 
Jmzd8 (edited ) src #3444

if you dont want me explaining it dont open this

so each digit will have its corresponding number that increases by itself every digit, so the first digit is 1 the second digit is 2 the third digit is 4 etc etc. calling these numbers "BN"

so kinda like this:

0 0 0 0 0 0 (binary)

32 16 8 4 2 1 (BNs)

so say you want to get the decimal number of the binary number 011010. you get the BNs corresponding with the places where there is a 1 and add them all together. like this:

0 1 1 0 1 0

16+8+4 = 26

im not really sure if you can do this with numbers higher than 63 (aka more than 6 binary digits)

taswelll (edited ) src #3445

this is right! this is how binary to decimal conversion works. the BNs are the the powers of two: each digit is the previous increased by itself => each digit is the previous multiplied by 2 => nth digit is 2 to the nth power.

positional base for a given B works the same way if you change "add all the powers of two where there is a one" to "add all the powers of K multiplied by the corresponding digit" (these are equivalent if K is 2; multiplying something by 0 is 0)

say you want to get the decimal number of the octal number 5756. let's get the powers that we need:

  • 83 = 512
  • 82 = 64
  • 81 = 8
  • 80 = 1

and 5*512 + 7*64 + 5*8 + 6*1 = 3054. this will work for every octal(/binary) number!

viba src #3446

beenary

caesar (edited ) src #3447

there's a faster algorithm

start with n = 1

if it's all zeroes the number is 0

ignore all digits up to and including the first 1 (left-to-right)

when you see a zero, 2n

when you see a one, 2n + 1

so 00000101:

n = 1 (1)01

n = 2 1(0)1

n = 4 + 1 10(1)

n = 5

big brother (bureaucrat) #3448
this post never existed.
taswelll (edited ) src #3449

yes! ax5 + bx4 + cx3 + dx2 + ex + f = f + x(e + x(d + x(c + x(b + ax))))

taswelll src #3450

""Horner's method""

caesar src #3451

oh cool, this is related to synthetic division (the best kind of polynomial division). but i discovered this algorithm myself

Jmzd8 (edited ) src #3452

>replying to taswelll

this is a better way of explaining it thanks

taswelll src #3454

have some powers of two, as a treat: 4294967296 2147483648 1073741824 536870912 268435456 134217728 67108864 33554432 16777216 8388608 4194304 2097152 1048576 524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1

amby src #3455

fun fact: this algorithm can be expanded to parse arbitrary bases (so long as you have a base-N digit to integer conversion)

start on the most significant digit
add it to an accumulator
multiply by the base
move to the next digit
repeat until you run out of digits

caesar src #3456

indeed! bn + d

taswelll src #3457

beaned

amby src #3458

beaned.......

i first saw that algorithm used in jonesforth btw

Jmzd8 src #3460

baked beans

ubq323 (bureaucrat) src #3461

yes, in the same way that in decimal, each digit from the right corresponds to the next highest power of ten, in binary each digit from the right corresponds to the next highest power of two. this is true of any base.

mb src #3462

synthetic division (the best kind of polynomial division).

but it's opaque - hard to see what it's actually doing at each step

caesar src #3463

long polynomial division is extremely complicated, i'd say it's more opaque for that reason

taswelll src #3464

it might be a bit more opaque but it's useful

taswelll src #3465

(i like useful)

caesar src #3466

divide 3x³ + 2x² + 4x + 7 by x² + 7x - 2 using long division (hard, extremely complicated. borderline impossible. useless)

do the same division using synthetic division (easy, not at all inconvenient, extremely simple. useful) (i also like useful)

gollark src #3467

REAL programmers just make computers do all division tasks.

mb src #3468

you can synthetically divide by polynomials with degrees higher than 1?

caesar src #3469

of course! it's all explained on the Wikipedia page for synthetic division

hopefully apioforum uses markdown so that link works

taswelll src #3470

apioforum uses markdown!

caesar src #3471

yay! c: bzzzzzzzzzt

mb src #3472

done

               3x   - 19
             --------------------------
x^2 + 7x - 2 ) 3x^3 +  2x^2 +   4x +  7
               3x^3 + 21x^2 -   6x
               -------------------
                     -19x^2 +  10x +  7
                     -19x^2 - 133x + 38
                     ------------------
                              143x - 31
Incoherent (edited ) src #3480

ok but consider

       3    2     4     7
   2 |            6   -38
-7   |    -21   133
     --------------------
       3  -19 | 143   -31

3x - 19 R 143x -31

please log in to reply to this thread