Karb0n's blog

Bigint ( II )

2004-11-13T08:09:00.000-08:00

Another way could be distributing the bits of the binary number over built-in types ( btw, from now on, I'll focus on C++ ), example:
We have a number 4903662431, which is 100100100010001111111001101011111in binary, and we distribute it over unsigned chars ( 8 bits most of the time ):

|00000001| |00100100| |01000111| |11110011| |01011111|
| char 1 | | char 2 | | char 3 | | char 4 | | char 5 |

See, we divide it in chunks of 8 bits going from the right to left.

Now we can easly add two numbers using less memory, and faster. The process is easy: you take the right most char from a number and the char in that in the same position from the other int and just add them together using the processor, since the result is moduled to the maximum size of the char ( in this case 256 ( 2^8 ) ) we dont have to worry about anything but the remainder. When you add in binary, if the result is bigger than 1 then you add add a 1 to the next digit, so same thing here, but how do we know when something is going to be bigger than 256? one option could be puting the result in a bigger variable, an int for example, but if we want to optimize our bigint to the maximum we'll want to use the biggest variable for adding. Another possibility is algebra, say we have 2 number a and b, and a third number c representing the maximum size, when is a + b >= c ? well easy: a+b >= c => a >= c-b, see, here we are not using numbers bigger than c.

So now that we have adding implemented, we can quickly make the multiplication and substraction, the multiplication of a times b is a summed b times so thats easy. And substraction is just like the sum but changing some minor differences.

tbc

Bigint Ideas ( I )

2004-11-11T07:03:00.000-08:00

This is a series of articles about operating with big numbers ( numbers bigger than the maximum size of a built-in type )

1. The most simple (binary)
A first aproach would be converting both number to binary and implement binary sum. This is quite easy but it could be faster and use less memory.

tbc

Sims 2

2004-10-13T15:39:00.000-07:00

Cool I just got the Sims 2 =D, lol=P

Variable Storing in memory (C++)

2004-10-11T13:40:00.000-07:00

In C++ you have three places where you can store variables:

Register
Stack
Heap

Each of them have their own advatnages and disadvantages which I'll cover here.
Nowadays the register is not often used (correct me if I'm wrong) , but when you can really use it (at very low level), it's the best place to store small variables that you will use a lot and that need to be fast, that is because the registers are directly managed by the processor, it doesn't have to access the RAM so it's very fast, however, you won't be able to store data that is too big and you have a limited amount of registers.

When you create a variable in a function and don't add anything else but the type, the variable is stored in the stack (this type of variables are called auto (ex: auto int myint = 0), and is the default for all local variables). Think of the stack as a pile of papers, you can read the top of the pile, you can trash the top of the pile, you can move the top paper and read the next one, etc. So, the stack is relatevly fast and can be used for most things without any problems, and in most cases, it's best way of storing variables, they are created and initialized when the program gets to the function where they're defined and are destroyed when the function ends. However, as everything, it has it's limitations, for example, you can't have too many (or too big) auto variables because you'll overload the stack, which isn't good hehe.

And finally, heap variables. This variables are stored on plain RAM and thats because they're the slowest (considering the speed of registers and the stack) but the good thing is that you have a lot space (well this depends on the ammount of RAM available). This type of variables are created with the operator new and destroyed with delete or free, they don't die when the function ends which can make memory leaking problems, but it's the best place of storing big variables and actively controlling their lifetime.

Missuses of the types of variables:
When you make a function that returns a pointer, for example:
//-----------------------
char * myfunc( const char some_arg )
{
char * myvar;

myvar = "Some string";
return myvar;
}
//-----------------------
The variable myvar is destroyed at the end of the function so the the pointer will be pointing to a non-existing locations. This might work as expected, my not work or might just exit giving you a memory violating error because you're triying to read protected memory. This is one of the worst errors a programmer can make, because as I said, it might work some times and he/she won't notice it until it becomes a huge problem and has to spend hours debugging the application.

TicTacToe

2004-10-08T15:33:00.000-07:00

Well, I just installed my new Visual Studio .NET and to retake my C++ skills i tried to make a tictactoe game. I wanted to make one cause I never made any AI-related projects. Anyway, i finished it (faster than i thought) today, it doesn't have a nice GUI or anything but that wasn't the purpose, the purpose was to make an inbincible TicTacToe AI player and that worked =D. Lets see if posting images works hehe:

[Ok i have to find some image host, i don't really like Hello's system...]