|
This forum is for asking questions. What you've got there looks more like a Tip. 
Submit a new Article - CodeProject[^]
You might also want to see how your code compares to the built-in BigInteger structure[^].
Eric Lippert did a series of blog posts[^] covering how you could implement integer operations without using the built-in number types, which is also worth a read.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Maybe but then it would need a bit more polish and I'm not sure it would fit, maybe a small blog post and carry with it some test results and discussion around it.
When I started thinking about how to solve this I had a nagging suspicion that there already was something readily available but I couldn't figure out what search terms to use to find it so I turned it in to code instead. That blog post was interesting I admire how some people can go so in-depth in a subject.
|
|
|
|
|
Member 11683251 wrote: Thinking about this really got me wondering about how others would choose to solve it instead.
My solution here[^].
Not the most efficient way
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
|
|
|
|
|
|
It may be a good idea to create a struct or class I'll call it LN which has a private vector with intergers VEC in the range of 0 to 9. The class has functions for Algebraic operations (+,-,*,/) to add two LN together. These functions must:
- determine the sizes of both VEC and resize accordingly.
- iterate though both VEC and execute the operation digit by digit.
Since vectors are dynamically allocated, you have virtually no cap on how many digits the number has (accept for RAM).
You'll have to replace all score related constant values in your code with LN's
I'm not sure how your game mechanics are designed, but if you have many hundreds of entities which add some constant value per second, it might be a good idea to have a single variable X which is added to the game score S every second, instead of iterating through all entities and adding the constant value to S. That is, when an entity is created, it adds it value per second constant E to X and when the entity is destroyed it subtracts E from X.
In every game step you then add X to S. This therefore only requires a single addition operation per game step and of course an addition operation when creating or destroying an entity.
|
|
|
|
|
Concerning the situation that might arise if you have hundreds of entities I figured that I could just do some approximations. The most important parts would be those entities that's closest to the current largest number in the bank so to speak.
If you have one entity that adds say 10^70 you it I could just go over everything below say 10^60 to calculate what to add per second for all those entities instead of doing 60 different calculations.
So far I'm not working on creating a game but this kinda grew from curiosity but I did some testing and 100 different entities, one for each level up to 10^100 was just a few ms. No graphics or anything else but even if I kept increasing it would be a while before there would be a performance hit. For a mobile app it might me more important but my home computer doesn't have a high end cpu so I was quite happy with the current performance.
There is a game called clicker heroes and the highest I ever came in that game was in the span of 10^130.
There are so many of these games out there and they mainly target mobile with in game purchases which costs exorbitant amounts of money. While I see the allure of these games where the amount of in game points you accumulate while you are idle and can just pop in every once in a while to spend and increase the gathering rate I find it hard to comprehend how people can justify dropping 100$ > for in game credits.
I'll see if I make an implementation of your suggestion of vectors if I got the time but it's always interesting to compare different solutions. If I do I'll make a comparison with one of the string based methods too.
|
|
|
|
|
It sounds like you need arbitrary-precision numbers.
With C-1999 or C++2011, you are guaranteed to have a 64-bit built-in type. If you limit yourself to "digits" containing 9 decimal digits (they fit into 32 bits), you can perform the four basic arithmetic operations with "digits" that are easily converted to decimal notation.
The following article (printed in Dr. Dobb's Journal in August 1992; includes source code) should get you started: Multiple-Precision Arithmetic in C | Dr Dobb's[^]
If you have an important point to make, don't try to be subtle or clever. Use a pile driver. Hit the point once. Then come back and hit it again. Then hit it a third time - a tremendous whack.
--Winston Churchill
|
|
|
|
|
i've got this homework problem which i tried to solve and didnt succeed so far. it goes like this:
Given k sets of integers A1,A2,..,Ak of total size O(n), you should determine whether exist a1A1, a2A2,...,akAk, such that a1+a2+..+ak-1 =ak. Your algorithm should run in Tk(n) time, where Tk(n) = O(n^(k/2)*log n) for even k, and O(n^((k+1)/2)) for odd values of k.
|
|
|
|
|
If you want help then you need to make some effort. No one here is going to do all your work for you.
|
|
|
|
|
I have to implement 3 data compression algorithms. I was thinking about LZW, Deflate and Bzip2. I can't find any good documentation for these algorithms. Do you know any data compression algorithms with good documentation, samples etc.?
|
|
|
|
|
I find that extremely hard to believe. A TON of documentation and discussion comes up with a simple Google for "LZW compression algorithm" "Deflate compression algorithm" and "bzip2 compression algorithm".
If you were looking for copy'n'paste code, yeah, that's going to get you a failing grade in class.
|
|
|
|
|
Agreed
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Member 12146827 wrote: I can't find any good documentation for these algorithms.
Learn to use Google ! really !
Member 12146827 wrote: Do you know any data compression algorithms with good documentation, samples etc.?
Yes, but your claims are just impossible, so you will have to search again. Don't fool us, April fools was 1 week ago.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Run-length encoding is a very simple one. It will save you some work by substituting it for one of the complex ones you mentioned.
|
|
|
|
|
|
Can anyone say which subjects and chapters in mathematics I need to know (thorough or basic) for learning algorithms? Also help me find a book on this mathematical subjects and a good book on algorithms for beginner?
|
|
|
|
|
If you type "algorithms" into Google you will find a wealth of information.
|
|
|
|
|
The information on google is all about how to make them, But I want the mathematics needed for it and there's no clear answer i got on google for that reason.
|
|
|
|
|
If you go and do some reading on the subject you will discover where the gaps in your knowledge are.
|
|
|
|
|
The general definition of "algorithm", in simple terms, is: A sequence of instructions to solve a problem. I can write an algorithm for how to clean my house. Or for picking apples from a tree. Or for flying a plane. There are as many potential algorithms as there are ideas what to do in this world and the variety of required skills to handle all of them is vast. The same holds true when entering the domain of computer science: There are algorithms for all sorts of stuff. Obviously, logical thinking and some sense for numbers won't hurt. In fact, most algorithms I've come across should be understandable by non-computer scientists if only written down in normal language instead of a programming language. Of course there are algorithms for which you will need very specific mathematical knowledge but the intersection of required skills for understanding arbitrary algorithms remains as simple as: Logical thinking and some sense for numbers.
If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson
|
|
|
|
|
The guy behind C++ wrote two books,
The C++ Programming Language is something I believe any serious C++ connoisseur should have chewed on for longer periods of time.
Algorithms in a Nutshell by George T. Heineman, and others is something I just started to read, and so far its good.
|
|
|
|
|
Algebra is the most important, since everything is based on it. Graph theory helps develop the kind of reasoning you need for algorithms. I've found linear algebra useful for real-world algorithms I've had to implement, but it depends on the domain you're working in.
|
|
|
|
|
I'm looking for an algorithm to find all the possible combinations of meetings (details in attached photo). I would like to introduce the teams algorithm calculates all threrefore combinations of matches, or better yet, I could enter the value to the team as the level of play by all the teams and I got all the options from the most probably
Tournament tree: http://prntscr.com/aoukzm[^]
Sorry for my english 
|
|
|
|
|
Eric Lippert did a series of blog posts on generating permutations and combinations in C#:
permutations | Fabulous adventures in coding[^]
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Check out my "Alternative Tip": Subset - Sum Problem with Numeric Collections [^]
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
