No Description
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Alextopher 6cf4cf7b86 Cleaning up project 3 months ago
.gitignore Cleaning up project 3 months ago
Makefile Removed .o files from git 3 months ago
README.md Tidy up README 3 months ago
backup.c Finished README and removed debug statements 3 months ago
bigint.c Fixed for polaris 3 months ago
bigint.h Added Exponentiation in O(log(N)) multiplications! 3 months ago
bigint_compare.c Fixed logic error in BigInt_ls() 3 months ago
bigint_pow.c Finished README and removed debug statements 3 months ago
in.txt Added Exponentiation in O(log(N)) multiplications! 3 months ago
list.c Add the Shunting Yard Algorithm correctly (I think) 5 months ago
list.h Add the Shunting Yard Algorithm correctly (I think) 5 months ago
main.c Finished README and removed debug statements 3 months ago
parse.c Fixed for polaris 3 months ago
parse.h Add parsing code and move sya out of main into parsing section. Start basic parser and update Makefile to always enable debugging 3 months ago
queue.c Make program work again like it did before, except with better data structures 5 months ago
queue.h Make much better and more efficient queue 5 months ago
stack.h Make stacks better 5 months ago

README.md

Infinity Calculator

Build and run with make 1>>/dev/null && ./calc in.txt only the first line of in.txt is calculated.

Ryan Stewart and Christopher Mahoney

For assignment two we wrote 2 parts. A tokenizer that uses the shunting yard algorithm to parse inputs and a bigint library that handles arithmetic.

The gist of how bigints are implemented is that we use a doubly linked list of uint32_t’s. Then we limit each node to 108-1. (99999999). This way, when perform arithmetic operations we can cast each node to a uint64_t. Since (232-1) * (232-1) < (264-1) we’ll never have overflow. We decided to limit each node to 108-1 so that we can efficiently print bigints with fprintf.

From here we implemented the arithmetic operations as if you would do them in grade school. However, instead of memorizing the results of operators for single digits we can use the ALU to efficiently give us results of 8 digit by 8 digit operations. That’s to say if n is the length of the inputs addition and subtraction are O(n) and multiplication is O(n2).

Extras: The bigint library natively supports negative numbers and the tokenizer can parse most situations with negatives. There are some strange situations (especially with parenthesis) where parsing negatives can fail. For example, something like (-3+5)* -3 will work, but (-3+5) * (-3) would break.

We also implemented exponentiation in O(log(n)) multiplications. Using a combination of Addition-chain exponentiation and modified Exponentiation by squaring. On average each digit in the exponent is processed in 7 multiplications. The best case is 4 if the digit is 0 and worst is 9 if the digit is 7 or 9.

Note: We decided to write our own tokenizer so we could get more familiar with that aspect of CS. If you read into the tokenizer you’ll see it is bounded in the length of the strings it can load. In practice you would need Zettabytes of memory to ever load such a string and we could always bump up to a 128 bit number and you’d need 565000 mols of ram. It could also have been written to work around this, but under the time constraint that wasn’t logical to do. Either way, we also included a modified version of the original finite calculator tokenizer which you can compile with gcc backup.c bigint.c bigint_compare.c -o backup. backup.c does not support exponentiation or reading negatives from stdin.