Saturday, October 30, 2004

BigInt Division

Mohn suggested sharing some of the BigInt code. The most interesting method I wrote was for division. And it is highly in-efficient, but I feel interesting. The general long division learnt in Algebra class if implemented is more efficient.

Assume that the other BigInt operations like <, *, - etc have already been implemented. I'll try to add descriptive comments within the code. (something which I should make a practice!!)

We were asked to implement a BigInt containing upto 100 digits. So I used a vector for that and a bool for sign of the number.

Here goes...

BigInt BigInt::
operator/(const BigInt& rhs) {
//hard code for RHS == zero
BigInt* zeroBigInt = new BigInt(0);
if ( (*this) == (*zeroBigInt) ) {
return *zeroBigInt;
}
//create copies of both lhs and rhs without sign
//set the sign of the answer later
//from now, lhs and rhs are the positive values of the numbers
BigInt* tempThis = new BigInt(*this);
tempThis->sign = true;
BigInt* tempRhs = new BigInt(rhs);
tempRhs->sign = true;
//if lhs < rhs value return 0
if ( (*tempThis)<(*tempRhs) ) {
delete tempThis;
delete tempRhs;
return *zeroBigInt;
}
//int quotient = 0;
//int factor = 0;
BigInt* quotient = new BigInt(0);

//get number of digits of lhs and rhs
int tempThisSize = tempThis->bigInt->size();
int tempRhsSize = tempRhs->bigInt->size();

//the difference between the two sizes should be atleast 2 digits
//tempThisSize will be decremented in the loop
while ( (tempThisSize) > (tempRhsSize+1) ){
//get the greatest factor of ten which is 2 digits smaller than lhs
BigInt* factor = new BigInt(1);
BigInt* tenBigInt = new BigInt(10);
for (int i=0; i<(tempThisSize-tempRhsSize-1); i++){
(*factor) = (*factor) * (*tenBigInt);
}
//cout << "factor " << (*factor) << endl;
(*quotient) = (*quotient) + (*factor);

//factorTemp is a copy of factor
BigInt* factorTemp = new BigInt(*factor);

//now increment the quotient by factor
//assume that we obtained a factor of 100 earlier
//in this step quotient is incremented by values of 100
//as 200, 300, .. till the muliplication tempThis is just exceeded
while( (*tempThis) >= (*zeroBigInt) ) {
(*tempThis) = (*tempThis) - ( (*factorTemp) * (*tempRhs) );
(*quotient) = (*quotient) + (*factor);
//cout << quotient << " " << (*tempThis) << " " << (*factorTemp) << endl;
}
//as a factor just higher than required has been taken
//perform a rollback
(*tempThis) = (*tempThis) + ( (*factorTemp) * (*tempRhs) );
(*quotient) = (*quotient) - (*factor) - (*factor);
delete tenBigInt;
delete factor;
delete factorTemp;
//cout << (*quotient) << " " << (*tempThis) << " " << endl;
//keep reducing tempThisSize
//if the earlier factor was 1000, now 100 can be generated
//so approaching the correct value
tempThisSize--;
}

//cout << "finished factor part!!" << endl;
//now to division by simple subtraction
//in the worst case, we'll have perform subtraction 99 times
BigInt* oneBigInt = new BigInt(1);
while ( (*tempThis) >= (*zeroBigInt) ) {
(*tempThis) = (*tempThis) - (*tempRhs);
(*quotient) = (*quotient) + (*oneBigInt);
//cout << (*quotient) << endl;
}
(*quotient) = (*quotient) - (*oneBigInt);
delete oneBigInt;

//set the sign of the output number
if ( (this->sign)==(rhs.sign) ) {
quotient->sign = true;
} else {
quotient->sign = false;
}

//some housekeeping and return
delete zeroBigInt;
delete tempThis;
delete tempRhs;
return *quotient;
}

Could have obtained a better perf if I created all the temporary BigInt's on the stack. Any more pointers? Any different algo's?

Monday, October 25, 2004

Re: C#

In the current module we are being taught programming in C/C++. C was just 2 sessions. C++ has more sessions but still really fast. And we are covering the new std C++. One of the C++ assignments is to create a Big Integer (BigInt) data type. The BigInt can have upto 100 digits and we are supposed to overload operators for < , > , == , +, - , / , % and few others. Just completed this one and division (/) has been amazing to code!!

I had to create a BigInteger in my "Generic Programming and the STL" class too. I'd be quite interested in seeing your code. I'll send you mine if you want.

I've always wanted to learn more programming languages. I think we agree that to be a complete dev have to know more than a particular lang. Good to appreciate design of each lang. Its just that I've been too lazy. Once you've entered the comfort zone with a lang, its hard to get out.

C++ has been a good experience. Lots to learn still but seen some really cool stuff. I dunno if I'll ever do stuff like python etc..


Yup, I think it's important not only to learn different languages, but also different paradigms like procedural, object oriented, generic etc... Also different types like functional languages (Haskell) and dynamically typed langauges (Python). Maybe you won't use it day to day, but it's always good to have that perspective.

I guess it's a question of time and priority. Learning different languages is fine, but you need to specialize in one or two which will be your bread and butter. And something like C++ it's no easy task. Rest are the "good to know" type.

There's a limit to how much you can understand by reading.

Couldn't have said it any better myself. In reading vs actual coding, there is a world of difference.

Google's browser plans

http://mozillanews.org/?article_date=2004-10-19+01-52-31

All speculation of course. But if they do eventually release something like that it would be the ultimate Windows/Web hybrid application. Seems like they are will be just tieing all their web properties into a client app.

Sunday, October 10, 2004

Re: C# ?

what's Mgpt? So are they going to teach you C/C++ in this next module or just use it for your programming?

Mgpt is one of the assessment methods here at Ncb. You'll get lots of info here . To put it simply, is a sort of a topcoder puzzle solving contest. Complexity of problems varies from "very difficult" to "writing a compiler is easier" levels. We have to clear Mgpt's for two modules, Java programming and Data Structures using Java. Generally only 3-4 students clear both in the entire year.

In the current module we are being taught programming in C/C++. C was just 2 sessions. C++ has more sessions but still really fast. And we are covering the new std C++. One of the C++ assignments is to create a Big Integer (BigInt) data type. The BigInt can have upto 100 digits and we are supposed to overload operators for < , > , == , +, - , / , % and few others. Just completed this one and division (/) has been amazing to code!!

In the next modules we have to create projects and no assignment problems as such. In those we can choose any language of implementation, Java or C++. No prizes for guessing what I'll prefer.


Just for an overview - C# programming

I have a super huge grin on me face. You don't know how happy this made me. Change is good :-)


I've always wanted to learn more programming languages. I think we agree that to be a complete dev have to know more than a particular lang. Good to appreciate design of each lang. Its just that I've been too lazy. Once you've entered the comfort zone with a lang, its hard to get out.

C++ has been a good experience. Lots to learn still but seen some really cool stuff. I dunno if I'll ever do stuff like python etc..


So hope that cleared some stuff up. What are your impressions of .NET from the book. I've been blogging a lot about this stuff so you should be familiar with some of it already - atleast I hope.

I had to switch to C++ so didn't do much. Most of the explanations you gave caused me to wonder.. what happens in Java. So I'll probably research on this for some time.

All your blogs on C# have been super helpful. I still have a few doubts, but those will get fixed only when I start coding. There's a limit to how much you can understand by reading.

Wednesday, October 06, 2004

Google's domain registrations

There was an article on slashdot regarding the registration of gbrowser.com. Some dude who was as early investor in google said that they weren't going to be entering the newly emerged browser wars. Check out these comments...

Now it makes you wonder why Google registered gbrowser.com?

  >> No it doesn't. They also registered googlesucks.com, but I don't
  >> think they feel that way about themselves.

    >> They registered Googlesucks.com? This is clear evidence
    >> they're entering the vacuum cleaner market!

      >> Crap! I was hoping it was an adult content
      >> search engine :(

Saturday, October 02, 2004