|
That's unusual and I couldn't find a simple solution, but I found a way that at least removes the loops.
static int SpecialModulo(int x)
{
x = x % 12;
if (x < 0)
return x < -7 ? x + 12 : x;
else
return (x & 7) - ((x & 8) >> 1);
}
|
|
|
|
|
(x & 7) - ((x & 8) >> 1);
Could you explain this line of code? I seriously don't know what does it do.
Greetings - Jacek
|
|
|
|
|
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.
|
|
|
|
|