Author Topic: BigNumNum Cruncher  (Read 30510 times)

0 Members and 1 Guest are viewing this topic.

Offline lkj

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 485
  • Rating: +58/-1
    • View Profile
Re: [Ndless] BigNumNum Cruncher
« Reply #30 on: January 18, 2012, 02:26:14 pm »
The problem is that a power of two can't be odd like in the second picture.
Have you some code?

Offline Hayleia

  • Programming Absol
  • Coder Of Tomorrow
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3367
  • Rating: +393/-7
    • View Profile
Re: [Ndless] BigNumNum Cruncher
« Reply #31 on: January 18, 2012, 02:43:17 pm »
ah, yes, a power of two that terminates by a 9 O.o
I own: 83+ ; 84+SE ; 76.fr ; CX CAS ; Prizm ; 84+CSE
Sorry if I answer with something that seems unrelated, English is not my primary language and I might not have understood well. Sorry if I make English mistakes too.

click here to know where you got your last +1s

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: [Ndless] BigNumNum Cruncher
« Reply #32 on: January 18, 2012, 06:36:28 pm »
I actually programmed it to use the "..." when the entire output is too large to fit.
The first picture (showing 2155) is correct, while the second one, 2210, is not. I noticed that it always outputs a number with a lot of 2809's and 2810's when it's not correct.

There is a part of my program that might be screwing up. One of the parameters my power function takes in is an array of ints that will be the output.
Code: [Select]
int numPow(int in1[], int in2[], int output[], int in1len, int in2len)For that parameter (called output[]), I pass it the pointer to an array, and the array has only one int in it.
Code: [Select]
int *ans = malloc(4); // One int
int ansLen = numPow(in1, in2, ans, numInts1, numInts2);
The power function keeps calling my multiplication function, and resizes the array whenever it needs to. (Now that I think about it, this might not be so smart)

I'm thinking that if the array grows too large, and it has to move to a different address, my pointer (named ans) won't update to the new address, so it will point to the old one, which is now full of garbage.

Also, (Not really related) If you have:
Code: [Select]
int a;
int b = 2000000000; // Still within range
int c = 2000000000; // Still within range
a  = (b * c) % 10000000000; // Last 10 digits of the product
Does that work, or will it cause overflow? I am wondering because right now, I am storing numbers as arrays of ints with 4 digits in each int, which is quite inefficient.

Are you wondering who Sammy is? My avatar is Sammy.
   

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: [Ndless] BigNumNum Cruncher
« Reply #33 on: January 18, 2012, 08:49:23 pm »
YESSS!!!

It was what I thought - the array grew too large and the pointer ended up pointing to some random section of RAM.

Behold - the largest numbers ever computed on the Nspire!
Note: it took around 3-4 seconds to do 29001

Are you wondering who Sammy is? My avatar is Sammy.
   

Offline Hayleia

  • Programming Absol
  • Coder Of Tomorrow
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3367
  • Rating: +393/-7
    • View Profile
Re: [Ndless] BigNumNum Cruncher
« Reply #34 on: January 20, 2012, 03:45:55 pm »
Great job ! :D
This will be very useful for arithmetics. You know when they ask you "what is the relainder when you divide 29001 by 193 ?" and you have to find a power n of 2 with 2n==1[193] because they think the calc is slow, with your engine, you just write the calculus and it is done :P
I own: 83+ ; 84+SE ; 76.fr ; CX CAS ; Prizm ; 84+CSE
Sorry if I answer with something that seems unrelated, English is not my primary language and I might not have understood well. Sorry if I make English mistakes too.

click here to know where you got your last +1s

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: BigNumNum Cruncher
« Reply #35 on: January 20, 2012, 05:05:13 pm »
Thanks! :)

I do a lot of math contests, and although the Nspire has helped a lot in them (at least the ones where calculators are allowed) I always dreamed of something more powerful, something that could answer a question like, "find the sum of the digits of 800!"

Are you wondering who Sammy is? My avatar is Sammy.
   

Offline lkj

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 485
  • Rating: +58/-1
    • View Profile
Re: BigNumNum Cruncher
« Reply #36 on: January 20, 2012, 07:17:14 pm »
Also, (Not really related) If you have:
Code: [Select]
int a;
int b = 2000000000; // Still within range
int c = 2000000000; // Still within range
a  = (b * c) % 10000000000; // Last 10 digits of the product
Does that work, or will it cause overflow? I am wondering because right now, I am storing numbers as arrays of ints with 4 digits in each int, which is quite inefficient.

Yes, it will overflow, my compiler gives a warning.

Why do you only store 4 digits in one int, and not more?

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: BigNumNum Cruncher
« Reply #37 on: January 21, 2012, 09:13:40 am »
If I store x digits per int, I only want the last x digits of a product (or sum or difference) and send the rest as a carry. That means all the numbers I get as results will be in the range of an int, but during the intermediate steps, some numbers will come out that don't fit in the integer range. For example, if I store 10 digits per int, and multiply them, the carry will be within range, and the last 10 digits will also be in range, but the product of the two numbers itself won't be. Storing 4 digits per int is the max that keeps all multiplications within range of an int.

Are you wondering who Sammy is? My avatar is Sammy.
   

Offline steelfirez

  • LV1 Newcomer (Next: 20)
  • *
  • Posts: 8
  • Rating: +0/-0
    • View Profile
Re: BigNumNum Cruncher
« Reply #38 on: January 23, 2012, 07:47:21 pm »
That's pretty cool. I participate in math contests a lot, and this would be really helpful. I'll type up some stuff later.

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: BigNumNum Cruncher
« Reply #39 on: January 28, 2012, 06:40:21 pm »
Version 0.16a: multiplication is around 20% faster, and a bug was fixed that allowed exponents to only be up to four digits in length.

More importantly, the exponentiation algorithm has been improved significantly - it now uses exponentiation by squaring instead of the naive method. The calculation times grow much slower now, and the difference in speed grows larger as the exponent grows. Here's a chart comparing speeds of 0.15a and 0.16a doing powers of two:

Are you wondering who Sammy is? My avatar is Sammy.
   

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: BigNumNum Cruncher
« Reply #40 on: February 20, 2012, 02:27:27 pm »
I haven't had much time to work on my project, but Winter Break = time to code :)
My checklist of things to do:
1. Allow large numbers to be viewed easily
2. Program:
   a. Sum of digits
   b. Trailing zero counter
   c. Factorial
   d. nCr
   e. Division
3. Make a menu system

By the way, did anyone take the AMC 10/12? How did you do?

Are you wondering who Sammy is? My avatar is Sammy.
   

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: BigNumNum Cruncher
« Reply #41 on: February 21, 2012, 05:03:36 pm »
Version 0.17a now with sum of digits completed. Unfortunately, this function won't be very useful until I program it so that the other input lines can be used (right now you can only type in line A) Also, I changed it so each input line is identified by number instead of letter.

Are you wondering who Sammy is? My avatar is Sammy.
   

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: BigNumNum Cruncher
« Reply #42 on: February 26, 2012, 09:46:22 am »
I made a custom radical sign character :)
It currently replaces the "1" character, so that's why the version number is so funny. :P

Meanwhile, I removed the memory usage indicator because it would be hard to program and useless, and I'm also working on porting GMP so I don't have to use my silly slow math algorithms. If that turns out successful, I will stop using my own math functions and just focus on programming a GUI.
« Last Edit: February 26, 2012, 09:47:15 am by sammyMaX »

Are you wondering who Sammy is? My avatar is Sammy.
   

Offline ruler501

  • Meep
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2475
  • Rating: +66/-9
  • Crazy Programmer
    • View Profile
Re: BigNumNum Cruncher
« Reply #43 on: February 26, 2012, 01:03:53 pm »
Could you post the source for this? I'd like to see if I could help and/or just look at it

Great job btw
I currently don't do much, but I am a developer for a game you should totally try out called AssaultCube Reloaded download here https://assaultcuber.codeplex.com/
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCM/CS/M/S d- s++: a---- C++ UL++ P+ L++ E---- W++ N o? K- w-- o? !M V?
PS+ PE+ Y+ PGP++ t 5? X R tv-- b+++ DI+ D+ G++ e- h! !r y

Offline sammyMaX

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 204
  • Rating: +9/-0
    • View Profile
Re: BigNumNum Cruncher
« Reply #44 on: February 28, 2012, 08:01:16 pm »
Here's the source and stuff. I work with Ndless 1.7 because it is supported by Ncubate, which I use for debugging, so sorry if it's not compatible with what you use.

Are you wondering who Sammy is? My avatar is Sammy.