Skip to content

Instantly share code, notes, and snippets.

@Kreijstal
Created October 13, 2013 20:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Kreijstal/6967047 to your computer and use it in GitHub Desktop.
Save Kreijstal/6967047 to your computer and use it in GitHub Desktop.
OKAY, so we(me) want to convert base 2 into base10 (any base to any base), alright each digit is stored in an array so base10 number 2012 would be stored as [2,0,1,2] in the array, basically
There MUST NOT be intermidate values, this is because it should support arrays of absolutely any size.
And it's not base 2 and 10 exclusive, it should support any (reasonable) base
//bigint suggestions may be ignored, I do this for learning purposes and because I'm insane.
We have the value [1,0] (10 in binary, 2 in decimal) we have to somehow convert this value to [2];
What is the best solution for this?
Attempt 1
[1,0] is the initial array is base 2, we want it to convert it to base10
each value in each array equals 2^i*v (reverse index, whatever (using big endian)) multiplied by it's value.
first we convert the numeric number of the base, this is '2' into base 10, we have the value number '2' already, the function that converts base to other base, basically, takes the FromBase and the ToBase arguments, and the array where the data is
we try to convert value 2 into base 10;
first we do 10%2 it returns 2; We push this value into our base10 array
then we do 2/10 (Math floored) it returns 0, when it returns 0 it means there's no other value, so we continue;
now we loop the base 2 array backwards, at the first iteration we get the number 0.
we do (2^i)*v (we could check if it's 0 to skip this part) (i is 0 because it's the first index, v is the value which is 0 too)
We get 0, we add this value to our base10 array
we move on, we do (2^i)*v we get something different now, i is 1 because it's the second index, v is 1 because it's the value we get
(2^1)*1, is surprise, 2.
We add this value to our array, the array we get now is... [2], wonderful.
There are some issues with this method, one is addition and one is exponentiation.
how can we do (b^i)*v when i is too high?
This is one issue, we have to fix, we must first of all make a function that takes 2 arrays, 1 works as a base, the second one as an exponent, and a numeric base, it returns the exponentiation result;
The first and easy way, (and because values aren't negative nor rational) is to do repeated multiplication, the issue with this is that it just takes too long.
FORTUNATELY, there are indeed some algorithms for exponentiation when these values aren't rational and non-negative, wikipedia has some, we'll use this.
However, these algorithms use this operations: Multiplication, division, addition, substraction we have to solve this issues with these arrays.
addition,multiplication and substraction are trivial, the issues is.. with division, now I'll post the functions for addition, multiplication and substraction
with substraction there comes somethnig into mind, what about negative numbers, should they be ignored? should I support somehow an state that states wheter they're negative or positive? INSTEAD of using the last bit?
MAYBE, maybe I'll use an unsigned value + a boolean to check whether they are positive and negative, however these functions don't really care about that, just yet.
Now that I think of it, this code could work in a bigint library or in a math library like mathematica does, or some shit like that.
Now we need to explain how addition works.
We want to add base values into same base values it doesn't matter the base, now
//ADDITION JS CODE
function addition(array1, array2, base) {
//I'll use a dumb algorithm, the one I was taught on schools, because is there any other algorithm that does it?
var result = [],
offset = 0; //Addition with bases, always has an offset
//FOR SIMPLICITY PURPOSES WE WILL USE LITTLE ENDIANESS
for (var i = 0, l1 = array1.length, l2 = array2.length; i < l2 || i < l1; i++) {//did you notice this part 'i++' I wonder how to make a counter if you can't even add, hah!
array1[i] |= 0; //This is pretty fucking nasty,I wonder what should I do instead. (you know converting undefineds to 0's)
array2[i] |= 0;
result.push((offset = array1[i] + array2[i] + offset) % base); //pretty straightforward I would think?
//There's a catch here... we're using additions to make an addition, that's retarded somehow, also there's other thing..
//wait how computers add an offset if they don't know how to add yet
//this will not support a spectrum of unreasonable bases :/
offset = (offset / base) | 0; //after thinking it for a while, fuck unreasonable bases. this is why I used |0 instead of Math.floor
//Wait a second here, am I.. dividing without.. even knowing how to ADD?! There's some flawed logic here!
}
if (offset) {//if offset, add the offset.
result.push(offset);
}
return result;
}
//SUBSTRACTION JS CODE
function substraction(array1, array2, base) {
//array1 must be larger than array2 oh gosh, I'll have to create a greater than algorithm don't I?
//I'll use an amazing.. algorithm, yes the one I learned at school, if this is the wrong way can someone pleease point a reasonable one?
var result = [],
offset = 0; //this offset is quite different from a normal offset isn't it, huh.
for (var i = 0, l = array1.length; i < array1.length; i++) {
array1[i] |= 0;//nasty sanitizing
array2[i] |= 0;
if (array1[i] >= (array2[i] + offset)) { //this is probably the worse way to do it. I don't want to ever save negative values, yes, JS have those natively but I don't really want to touch them, just imagine this isn't a real array it's a Uint8Array
result.push(array1[i] - (array2[i] + offset));
offset = 0;
} else {
result.push(base - ((array2[i] + offset) - array1[i])); //How computers know how to substract, if they don't know how to substract yet, huh?
offset = 1; //that's right, offset is boolean.
}
}
return result;
}
//yeah this gets boring with some time.
//I really don't think the "school" way is seriously the best way.
//Therfore I'll use a wikipedia to give me some insight in what multiplication algorithm will be best?
//apparently school way is best way, what a load of bs, well, let's do it.., sigh
//MULTIPLICATION JS CODE
function multiplication(array1, array2, base) {
var result = [],
offset = 0,
res;
for (var i = 0, l1 = array1.length, l2 = array2.length; i < l1; i++) { //did you notice this part 'i++' I wonder how to make a counter if you can't even add, hah!
for (var ii = 0; ii < l2; ii++) {
//console.log("i+ii",i+ii,i,ii)
result[i + ii] |= 0;
result[i + ii] += offset;
res = result[i + ii] + array1[i] * array2[ii];
//console.log("values",res)
result[i + ii] = res % base;
//console.log(base,res)
offset = (res / base) | 0;
}
}
//console.log("off",offset)
if (offset) result.push(offset);
return result;
}
//division!! this one is haaard, no really, I'd have no ide how to implement it.
//let's use wikipedia
//nope, well, the articles talks but I don't understand most of it, what do?
//DIVISION JS CODE
function division(array1,array2,base){
var result=[];
return result;
}
//CHECK ARRAY EQUALITY if the arrays are different bases it may give true and it obviously won't work
function checkIfarraysareEqual(a, b) {
var x;
if ((x = a.length) === b.length) {
for (var i = 0, l = a.length; i < l; i++) {
if (a[i] !== b[i]) return false;
}
} else return false;
return true;
}
//This is a test I made to check how to add without addition
function addition(a,b){//bitwise operators LOL
//wait for what I wanted to do, it needs a counter, but how can I count if I can't add.. LOL?!
//This is wht's called an ADD gate in electroniks you use other gates and stuff, it's quite interesting actually.
do{
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment