|
If it's above 7 (well, 7-15, but we have done mod 12 already), i.e. it has an 8 bit set, it drops the 8 bit (via the &7) and subtracts 4 (x&8 will be 8), i.e. subtracts 12. I would think that x-12 would be faster though so I'm not sure why it's written this way.
|
|
|
|
|
Because you shouldn't Always subtract 12, but only when it is bigger than 7. Of course a conditional would also work
|
|
|
|
|
Yes, I meant
if(x > 7) x -= 12;
... apologies for missing the first part. I still think that will be faster than the ands, shift and subtract, though it would be close.
|
|
|
|
|
Ok, so what you want to do is map numbers over 7 onto [-5, 7], and those below -7 onto [-7, 5]. Your modulo is 12 but the range size is 14, so there won't be a one liner with mod. I can make one with a ternary:
x += 12 * (((x < -7) ? 5 - x : (x > 7) ? -5 - x : 0) / 12);
... though, as above, this can overflow, and it is probably better to do
if(x < -7){
x = (x + 7) % 12;
if(x < -7) x += 12;
} else if(x > 7) {
x = (x - 7) % 12;
if(x > 7) x -= 12;
}
|
|
|
|
|
Yea that's probably better than mine..
|
|
|
|
|
Actually, it is impossible for x to exceed range (-12,12). I have changed from if to while "just in case", but I doubt there would be more than one iteration. So, since a solution with modulo seems to be very sophisticated and not clear then I decide to use a more readable form with while "loops".
I just though that there is a simple solution in form (x - a)%b+c which I missed.
Anyway, thanks for help. Sincerely, your modulo skills impressed me (that ternary thing is awbeatyful).
Greetings - Jacek
|
|
|
|
|
For a constrained range the simple version with ifs (I don't really recommend the ternary approach in production code, it's just fun to see what you can do with it) will be faster than any 'clever' approach with a modulo. Mod and div are extremely slow and a couple of branches to do the same task as one should win.
You shouldn't use the while loops if you have set your domain to (-12,12). They are adding an extra test for nothing, but worse, they are confusing to people reading the code (including yourself in three months) because it looks like the domain is unconstrained. If you're concerned you can put a range check and throw an exception (or language equivalent, this could be any C family language) if the input is outside the domain.
|
|
|
|
|
I started doing crazy things such as:
static int SpecialModulo(int x)
{
return (x & 7) - ((x & 8) >> 1) - ((x >> 31) & 4);
}
Trying to make a branchless version..
And then I realized.. why not just use a lookup table?
int[] table = new int[] { 0, 1, 2, 3, 4, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, -4, -3, -2, -1 };
x = table[x + 12];
|
|
|
|
|
int[] table = new int[] { 0, 1, 2, 3, 4, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, -4, -3, -2, -1 };
x = table[x + 12];
Nice. I think you missed %table.Length though.
Greetings - Jacek
|
|
|
|
|
Not if x is only in [-12, 12], which you said at some point..
As an alternative I have a slower way that only uses arithmetic (I just like doing that)
(((abs(x)+4)%12)-4)*sign(x)
int abs(int x)
{
int t = x >> 31;
return (x + t) ^ t;
}
int sign(int x)
{
return 1 | (x >> 31);
}
|
|
|
|
|
If x==12 then table[x+12]=table[24] is out of bounds. Also, without %, most of the "lookup table" would be wasted.
David1987 wrote: (I just like doing that)
Which is noticable. 
Greetings - Jacek
|
|
|
|
|
Jacek Gajek wrote: If x==12 then table[x+12]=table[24] is out of bounds.
Okay.. add one more item.
Jacek Gajek wrote: Also, without %, most of the "lookup table" would be wasted.
Would it be? x can be any value in [-12,12], right? That's pretty much all items in that table .. and one more yes, I missed the last one
|
|
|
|
|
Ummm, right. Thanks and good night!
Greetings - Jacek
|
|
|
|
|
So I'm trying to use the hash functions provided by .Net in C#. However the implementation they provide does not provide a way (at least, not easy to find) to where I can add bytes to update the current hash sum. Please note, I am NOT talking about using a stream. I need to be able to add from a byte array.
Yes, I have googled around for several hours trying to find a solution, so shut up.
I have a hard time believing that a solution does not already exist out there, as this seems like a necessity for any hash function. So please don't tell me something that "might" work or "should" work. I'm looking for a solution that is known to work.
Thanks for your help.
John
|
|
|
|
|
That's a remarkably obnoxious way to ask for help, especially for a relative newbie. And I suggest that you rephrase your question, as I can think of several interpretations of "add from a byte array."
Will Rogers never met me.
|
|
|
|
|
First off, I apologize. I was incredibly annoyed when I asked posted this, but this doesn't excuse me being rude. I'm sorry.
As an example, when using hash functions in C, there are normally 3 functions:
1) Initialize
2) Update
3) Finalize
I'm looking for the equivalent of update, where you can add more bytes to to be used. I can see now where the confusion lies in my first question.
Hope this clears things up, and again, sorry,
John
|
|
|
|
|
All of the .net hashes work this way; Maybe you should have used google; I found this on the very first search I entered.
http://msdn.microsoft.com/en-us/library/system.security.cryptography.hashalgorithm.transformblock.aspx[^]
In order to hash data one block at a time, you need to use the hash algorithm's ICrytpoTransform interface. This interface provides two methods of note:
TransformBlock(byte[] inputBuffer, int inputOffset, int inputCount, byte[] outputBuffer, byte[] outputOffset)
TransformFinalBlock(byte[] inputBuffer, int intputOffset, int intputCount)
|
|
|
|
|
You are talking about cryptographic hashes, like System.Security.Cryptography.SHA1[^] and friends?
ComputeHash takes a byte array. So I don't understand the question. You can't 'add bytes' to a hash, you need to rehash the modified full data.
If there is a stream solution (and I'm not really in the mood to search for one for you after the tone of your post) then you can use MemoryStream from your array of bytes.
|
|
|
|
|
What exact kind of hash function are you talking about?
Many can't be updated that way (eg SHA1)
|
|
|
|
|
Hello Everybody,
suppose
A = number of ones
B = number of zeros
C = A + B
now there will be total of X unique C-bit numbers in which A bits are 1 and B bits are 0
X = (C!) / (A! * B!)
example
A = 4
B = 2
C = 6
X = 6! / (4! * 2!) = 15
01 001111
02 010111
03 011011
04 011101
05 011110
06 100111
07 101011
08 101101
09 101110
10 110011
11 110101
12 110110
13 111001
14 111010
15 111100
now,
is there any algorithm by which we can find values of these X C-bit numbers with out going through each of C-bit numbers i.e
without using following method
for(i = 0; i < pow(2, C); ++i)
{
if i contains A 1s and B 0s then add i to list
}
thanks.
|
|
|
|
|
Never use pow(2,someint). It's inaccurate and slow. You might as well do 1<<someint
And yes, there is such an algorithm, you can quickly generate the next bit-permutation[^]. Just start out with (1<<k)-1 and keep using that permutation function until you have them all.
|
|
|
|
|
|
Hello Everybody,
I want some help from your side. Actually i m writing an Algorithm for Sewer Colony Optimization Algorithm.
In case of Ant Colony Optimization is generate a flow. But In case of Sewer Colony Algorithm this generate a Tree which Parent is Sink.
And Sewer is not pumped. It's just goes by gravity.
Thanks
If you can think then I Can.
|
|
|
|
|
A little clearer description of the problem space would be helpful, but in the meantime, look at the Hazen-Williams Equation[^] for full pipe flow, or Manning's Formula[^] for open channel gravity flows.
At equilibrium, pressures at each node must be equal, and the flow volume exiting the node must equal the sum of the individual flows entering it. For calculation purposes I would expect that it's safe to assume that each of the sources has infinite capacity, but if not, you have some additional complexity to deal with. I'm not clever enough to do it myself, but I'd love to see an article on the topic when you're done. 
Will Rogers never met me.
|
|
|
|
|
Hello,
I want ask you to read my algorithm for solving Knapsack Problem and tell me if i'm wrong or if there is similar algorithm
If you are interested, i can send you source code, description and etc.
Knapsack problem algorithm.
Nikolay Nedelchev Bulgaria, Sofia e-mail :
I. Integer item weight.
Let's review how the DP algorithm works and focus on the important points.
Let N be the item count, and M - the capacity of the knapsack. The DP algorithm constructs a table with dimensions M * N, and calculates for EVERY possible knapsack with capacity <= M all N possible solutions, for items (1), (1,2), (1,2,3)..(1,2..N), i.e Omega(M*N).
One of the bigger problems with this algorithm is that in practise it has to solve "similar problems", which give one and the same solution. Because knapsacks with capacities M-4 and M-5 can have identical solutions, but the DP algorithm has to calculate them both, no matter what.
Let's have a completely different look at the knapsack problem.
Let's ask ourselves how many knapsacks which are smaller or equal in capacity than M and have ONLY DIFFERENT BEST SOLUTIONS, exist(solutions with different total value and weight, all solutions with equal total weight and value are considered as a single solution, and only one of them is used, no matter which). Let these different solutions form the set S.
It's obvious that the size of S is <= M (eg: if M = 1000, there is no way that 1001 problems with different solutions exist, when there are 1000 possible knapsack capacities {M=1000})
Let's also note that the solution from S with largest value (and it's also the one with largest weight, because if a solution with greater weight and smaller value existed, it wouldn't be present in the set, because it wouldn’t be BEST solution for any knapsack) will be our solution for knapsack with capacity M.
This means that if we can build the set S with time and space complexity O(S*N) in sorted form, we can get to the solution of the initial problem by another O(1) operations and because S <= M, this algorithm would be better or at least equal (in the special cases) to the DP algorithm.
The Algorithm:
Let’s have a set of objects O={oi}, i = 1,2…n each object having a weight and value.
Let’s have a set of objects S = {si}, I = 1,2..m, each object being an unique subset of O.
Each object of S has value which is the total value of all the objects oi in the represented subset of O, and weight, formed in the same way.
S contains:
1. Every subset of O except those which have a smaller value than at least one of the other subsets with the same or smaller weights. (and except those which have same value with at least one of the other subsets with the smaller weights)
see Clarification
2. Only one of the subsets with exact same weights and values, no matter which.
Let S be sorted by descending weights.
The so formed set S, has the following properties:
Property A: The so defined set S contains all the possible best answers for all the possible knapsacks for which there is a valid solution.
Property B: Each object in S is the best answer for at least one possible knapsack.
Property C: The list is sorted by weight.
Property D: The list is sorted by value (because of 1.).
Let’s have a new object p of type O.
Let’s have a new set T = {ti} of type S, which contains all the objects from S, but each subset is augmented with the object p, so the value of each object of T, ti , is equal to the value of si plus the value of p. The same applies to the weight.
T has all the same properties A(*), B(*), C, D.
Let’s add p to T, as a singular subset in the right position, in order to preserve the sort order by weight.
The so formed set T has lost properties B and D, but has kept properties A(*) and C.
* It follows from Prop A, that the set T contains the solutions to all the possible knapsacks if t should be present in the solution.
As a reminder, S contains all the solutions if t should not be present.
So, we can create a new set S, which is formed from merging the old S and T, keeping with 1. and 2.
The new set S has all the properties A.B.C and D for the new set O including object p.
The time complexity of the construction of the new set S takes O(N) time, with N being equal to the size of the old set S.
If at the time of the execution of the so presented algorithm, all the O objects and the capacity of the knapsack are known, all the sets S can be optimized according to the currently found best solution and input information, i.e. we can add to points 1. and 2. a new point 3. That the weight of the subsets in S does not exceed the capacity of the knapsack and etc.
Because all the operations described here on S take a linear time, it follows that the overall time complexity of the algorithm is O(S1+S2+S3…SN) (the sum of the sizes of all the sets S i.e. from definition of S : m1 + m2… mn) .
Clarification to 1.
If we have o1(w = 2, v = 9) and o2(w = 4, v = 8).
Then S = { s1 = (o1) , s2 = ( o1 + o2) }
We do not need the o2 object as a singular subset and will never need the o2 object in a subset that does not contain the o1 object
NOTES:
1. With a suitable representation in memory, every object in S can take constant space and the solution can be extracted in O(n) time, n = size of solution. Also in general there is no need to keep all objects of all sets S.
2. If we compare this algorithm to the currently available dynamic programming algorithms we will note that the sum of all the sizes sets S which we have created, is smaller or equal to the size of the table, which we would have allocated (and calculated) during DP, in other words, the time and space complexities of the algorithm are always smaller or equal to the complexity of the DP algorithms
3. The algorithm can be used with all kinds of input data, including real, negative (as well as very big), etc, numbers as weights.
4. We don’t need to calculate the last set of subsets S
5. The algorithm can be easily transformed to the algorithm of Horowitz and Sahni.
Please tell me about errors and other uncertainties.
modified on Friday, July 1, 2011 12:07 PM
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
