|
does any one here have any idea of the possibility of creating a classified ad aggregation Algorithm, i am designing a new classified ad service and need in put. we will need such an Algorithm created if we are to move forward, any comments welcome. thanks.
M Bey
|
|
|
|
|
For the very large number like 2^2000 how do I calculate its value?
|
|
|
|
|
Use logarithms.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
|
|
|
|
|
|
To elaborate on Alan's suggestion...
Let's take a big power of 2, such as:
2 ^ 2000
We first re-express it using a power of 10:
10 ^ (2000 * log10 (2))
Which yields:
10 ^ 602.05999132796239042747778944899
But we want it re-expressed in the more useful form of: man * 10^exp, the scientific notation (just in case).
We know that x^(a+b) == (x^a) * (x^b), where x=10 and (conveniently) a and b can be the integer and the fractional parts of 602.05999132796239042747778944899
In other words:
10 ^ (602 + 0.05999132796239042747778944899) == (10 ^ 602) * (10 ^ 0.05999132796239042747778944899)
We can rearrange it in:
10 ^ 0.05999132796239042747778944899 * 10 ^ 602
Which yields:
1.1481306952742545242328332011881 * 10 ^ 602
And that's the result of 2 ^ 2000:
1.1481306952742545242328332011881e+602
You may calculate this with fixed math, but you won't get as many ULPs and it'll take more time. Either way you're going to get an approximation of the sought value.
The above also works with smaller powers.
A quick demonstration for:
5^3 = 125
Here:
5^3 = 10 ^ (3 * log10 (5))
5^3 = 10 ^ 2.0969100130080564143587833158265
5^3 = 10 ^ (2 + 0.0969100130080564143587833158265)
5^3 = (10 ^ 2) * (10 ^ 0.0969100130080564143587833158265)
5^3 = 10 ^ 0.0969100130080564143587833158265 * 10 ^ 2
5^3 = 1.2499999999999999999999999999985 * 10 ^ 2
5^3 = 1.2499999999999999999999999999985e+2
If we account for the rounding error it becomes familiar:
5^3 = 1.25e+2
5^3 = 125
[edited to improve explanation]
modified 23-Oct-12 6:43am.
|
|
|
|
|
my friend you can use the big integer class it helps you a lot to do such things.
|
|
|
|
|
Use binary:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000b
|
|
|
|
|
More seriously, an easy option is to work in base 1 billion, using an array of integers. Every integer will store 9 significant decimal digits.
It is a rather straightforward matter to implement a doubling algorithm, by means of long addition, as in the following quick Python code.
N= [0] * (Digits - 1) + [1] # Large number representation of 1
for Exponent in range(2000): # Double 2000 times
for Position in range(Digits): # For all digits
N[Position]= 2 * N[Position] # Double this digit
if N[Position] >= Base: # Detect carry out
N[Position]-= Base # Adjust the digit...
N[Position - 1]+= 1 # ... and carry out to the left one
print N
Output:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 114813069, 527425452, 423283320, 117768198, 402231770, 208869520, 47764273, 682576626, 139237031, 385665948, 631650626, 991844596, 463898746, 277344711, 896086305, 533142593, 135616665, 318539129, 989145312, 280000688, 779148240, 44871428, 926990063, 486244781, 615463646, 388363947, 317026040, 466353970, 904996558, 162398808, 944629605, 623311649, 536164221, 970332681, 344168908, 984458505, 602379484, 807914058, 900934776, 500429002, 716706625, 830522008, 132236281, 291761267, 883317206, 598995396, 418127021, 779858404, 42159853, 183251540, 889433902, 91920554, 957783589, 672039160, 81957216, 630582755, 380425583, 726015528, 348786419, 432054508, 915275783, 882625175, 435528800, 822842770, 817965453, 762184851, 149029376]
In reality, this algorithm uses a trick: a carry-in to a digit (from the right) will never cause a carry-out (to the left). This is because the doubled digits are even, at most 999999998, and can stand one incrementation. This allows us to process left-to-right. This property doesn't hold for plain addition where carries can propagate further.
A more efficient but a little more complex solution can be achieved by using a base conversion algorithm.
modified 3-Dec-12 6:44am.
|
|
|
|
|
There is actually a subtle bug in your code. If, on the last pass of your outer loop, one "digit" is == Base - 1 and you carry into it, you never get to carry out of it. If you write your inner loop backwards (or reverse your array), it all comes out in the wash... The point is that multiprecision add/subtract should be done "right to left" so multiplace carry propagation can occur naturally.
A small point, but still important. The one time it bit me, the code was in ROM inside tamper-proof enclosures. A real PITA to fix...
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
You are quite right, sorry for having mislead you.
This is the kind of "off by one" trap I too easily fall into. When I wrote this code I was indeed unsure in what way to go, and I just satisfied myself when I saw successful tests.
There is indeed no carry propagation here and this could have been avoided by careful proofreading: when the carry is made, it applies to digit Position-1, showing that propagation needs to be done by decreasing indexes.
Mea culpa.
How did you discover the flaw ?
|
|
|
|
|
YvesDaoust wrote: How did you discover the flaw ?
In my case, we were doing 32 bit arithmetic on an 8-bit processor. The little machine was attached to the memory system of its larger host, reading messages from there, processing them (cryptographically) and writing the results back. A nasty combination of buffer size and alignment meant that occasionally a block would be read from the wrong place, or, worse, written to the wrong place. Three of us spent a good week staring at code, running simulations and generally not seeing what was under our noses. In the 30-odd years since, I have been sensitised to that kind of bug.
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
Interesting. Given that you work with an 8 bits processor, base 100 could have been an option too.
But now I am getting quite puzzled as I believe that multiple carries are not possible: when you double a digit, this can cause a carry-out; in all cases you get an even digit, at most Base-2; for the same digit, the carry-in cannot cause an extra carry-out. Said differently, the doubling of digits generates all the carries-out it needs to, and my original algorithm is correct. On the opposite, merely reversing the traversal direction causes all carries-out to be unduly doubled.
|
|
|
|
|
The reason why I processed left to right is that the carry needs to be done after the doubling of the digit to the left.
modified 3-Dec-12 6:27am.
|
|
|
|
|
Hi All,
Lets see if this helps. I am reading back data from a device into a rich text box this is all working fine I can save out as a file fine, the data may contain multiple units so I need to check the first 8 bits to see if they are the same I can split them up fine it is how to store them. I don't really want to use separate text boxes so I was thinking of strings would this be a dumb idea as I don't want to cripple performance?
Glenn
|
|
|
|
|
Could you give some more info? Such as, what do those first 8 bits mean? What is splitting and why is it necessary? Why are text boxes involved?
|
|
|
|
|
The first 8 bits are a serial number of the read unit. The data is records, read as strings out of the unit. I am a the moment not splitting them just saving them as one file, this is where the spec is a little flaky and I am trying to have an answer ready if needed. If I use the method I was using the String.split method, I need to check the first 8 bits against a stored list, I was thinking of using rich text boxes to store the split reading in for a test and then using strings for the actual program. Firstly I need to declare an array of strings which in theory could be 1024 in size.
new string[] Serial_Numbers ={};
This I'm guessing from the green underlining is wrong but....
Glenn
|
|
|
|
|
string[] Serial_Numbers = something;
Ok, I still have absolutely no idea what the problem is or how to solve it, though
|
|
|
|
|
You would normally declare something like this as
string[] serial_numbers = new string[] {};Note, however, that you've just declared a zero length array, so you would have to resize it (which isn't the most efficient operation) whenever you want to use it. There are many more efficient ways to save the data - and which one you choose depends on what you want to do with it. You could use a List<string> or a Dictionary of strings and readings - which one you choose depends on what the ultimate purpose is of the readings.
|
|
|
|
|
Hmmm, the evil gods Malloc() & Calloc(), but I have already discovered that. The ultimate goal is to split the readings into separate files from the text property of a text box ie the box has output from the hand held in one rtb I was looking for a way to split the contents up. If the readings are say 12345678|AAA|BBBB|CCCCCC the next reading is 23456781|AAA|BBBB|CCCC at the moment the file is created with all the readings in one place. What I'm trying to is split up the data to separate files as the spec does say to do it that way but I can see problems with it if don't have a method, if I create the string array with the total number of records read from the unit that would get around that problem. If I use substring() as below:
foreach (string subString in rtbTestBox.Text.Split('\n'))
{
foreach (string subStringSerNo in subString.Split('|'))
{
if (subStringSerNo.Length == 7)
{
Serial_Numbers[serialNumberIndex] = subString;
MessageBox.Show(subString);
MessageBox.Show("Yaowwwser!!!", "", MessageBoxButtons.OK, MessageBoxIcon.Exclamation);
serialNumberIndex++;
}
}
and it should give me an array of readings which I can the search for differences in the serial number. If I then have the array of strings, the serial number is different I can place it in a different string if it's the same just append it.
Am I making any sense in my caffeine addled state!
Glenn
|
|
|
|
|
I see a few issues with this design.
First of all, you are using the RTB as the datasource - you really should use a proper structure for the data - you can add the data from this to your UI if you need, but you should start off with the idea that the data is the important thing (this also simplifies you saving out the data).
Secondly - if you need to display the data, you will find it easier to display it in a ListBox. Adding items into a ListBox takes a lot less time than adding data at the end of a large RTB.
I would be tempted to have a structure that represented a single reading, and then create a Dictionary using the serial number as the key, and a List of these readings as the value. That way, you can iterate over the Dictionary and save out the values to separate files.
|
|
|
|
|
Good advice.
When using a list box he may store the numerical serial number as item data.
|
|
|
|
|
Sorry didn't see your reply, I was messing with a test app. The issue I have knocked up I have some test data in a list box.
|
|
|
|
|
No need to say sorry. It's not a chat here.
If you already have a list box, you may use my suggestion. Then you can identify the device strings by querying the item data (e.g. write all strings for a specific device to a file).
|
|
|
|
|
After a bit of fiddling, I have a list box I can add the data to
1111111|16:11:52|08-10-12|0|0|00a8
now this is a sample returned from the unit, The serial number of what I am trying to sort are
11111111 I would like to get an opinion on whether or not using an array of strings the size of the total number of records on the unit is a good idea bearing in mind I have no idea what PC it is going to be run on. Here's hoping what I sent is good enough (one file)! (before you say it I know full well Hope & Pray are not viable options!  )
Glenn
|
|
|
|
|
If you add such strings to a list box you already have an array of strings. You can use the Find() method to find strings that begin with a specific serial numbers. You can implement a sort function to sort by the serial numbers.
I'm using C++ and did not have experience with .NET. Using MFC or Windows API functions, each item of a list box can be assigned a user data value. When setting this item data to the serial number, the list can be searched and sorted by these values which is much faster than searching/sorting using the strings (item text).
Performance depends on the max. number of items. You may raise a new question about this. May be someone else has experience with large list boxes. I think a few thousand items should be no problem.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
