Algorithms

contiguous bits algorithm.

5-Sep-07 22:09

ok, but it could be acceptable that the numbers repeats itself, it is only a sequence.
If you want to draw the images related to the fractals I'm thinking than you are not on the right way:
take the mandelbrot formula z(n+1)=z(n)^2+c
you do not have to prepare the sequence of z to draw the image, you have to study its convergence!
Fixing c, start from z=0 then you have to see if z(n) will escapes to infinity. You have to do this for many values of c (complex).
The image is only the real and imag part of c and the color is the first value of n that gives |z(n)|>2.

All this is true if my memory is well working Unsure | :~

Russell

Re: FRACTAL FORMULAS

Luc Pattyn4-Sep-07 23:06

Luc Pattyn

4-Sep-07 23:06

I don't know what your problem is, and I am not going to cover all those fractals.

Mandelbrot needs complex numbers (z = z*z + c needs a complex z and a complex c);
and the Mandelbrot set requires you iterate this formula with some constant c, a
variable initial value z0 of z (that's the point on the drawing), and then you calculate
how many iterations it takes to satisfy abs(z)>=2 to determine the "height" or color
of point z0.

There are several articles on Mandelbrot here on CodeProject; maybe on the others too.
The basic info probably is available on Wikipedia, if not just Google.

BTW: fractals make most sense when you plot them, just showing some numbers is
hiding their beauty for sure.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google

chandu0042-Sep-07 22:09

chandu004

2-Sep-07 22:09

i have a 16 bit variable(unsigned short).
now i want a best algorithm (function) which will do the following.
1.if contiguous bits at LSB are high then the function should return 1.
for example, consider the following bit patterns
0000000001111111
or
0000111111111111
or
0000000000000001
2.if continuous bits at MSB are high then the function should return 2.
for example,
1110000000000000 and so on.
3.other wise it should return 0 for the examoples such as
1010000000000011
0000011101010011 and so on
thanks in advance.
any more clarifications required, please get back.

Russell^'2-Sep-07 22:44

2-Sep-07 22:44

Test the int with this constant variables if you want to not use a for loop with SHIFTs and bit-comparing.

To return 1:

1111111111111110
1111111111111100
1111111111111000
...
1100000000000000
1000000000000000

to return 2:

0000000000000001
0000000000000011
...
0111111111111111

else return 0

Russell

cp98762-Sep-07 22:48

cp9876

2-Sep-07 22:48

There might be some nifty bit processing, but this should work with no more than about 6 comparisons (32 bits - 62 options)
8-bit version:

int fn(int x)
   {
   switch (x)
      case 0x01:
      case 0x03:
      case 0x07:
      case 0x0F:
      case 0x1F:
      case 0x3F:
      case 0x7F:
         return 1;
      case 0x80:
      case 0xC0:
      case 0xE0:
      case 0xF0:
      case 0xF8:
      case 0xFC:
      case 0xFE:
         return 1;
      default:
         return 0;
   }

I think compilers are quite good at optimizing this sort of code, but I have never tested it so I'd be interested in comments.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

Re: contiguous bits algorithm. [modified]

chandu0042-Sep-07 23:14

chandu004

2-Sep-07 23:14

thanks,
the above logic is simple and works as of now.
but the ultimate goal is to design a function in the following prototype.
int GetWordStatus(int word,int word length)
{
//code here
}
if the word length is certainly 8 or 16 or 32, then teh above logic is appropriate.
but the checking has to be done on the first specified number of bits. i.e. wordlength.
hope i dont need to give any example,
if required, i can.
thanku.

cp98763-Sep-07 0:04

cp9876

3-Sep-07 0:04

You should be able to extend this - do something like:

const int hi1 = {0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 0xE0, 0xC0, 0x80, 0};

int GetWordStatus(int word, int wordlength)
   {
   ASSERT(wordLength <= 8  &&  wordLength >= 0);
   int x = word & ~hi1[wordLength]; // may not be necessary depending on what data can be sent
   switch (x)
      {
      case 0x01:
      case 0x03:
      case 0x07:
      case 0x0F:
      case 0x1F:
      case 0x3F:
      case 0x7F:
         return 1;
      }
   x = word | hi1[wordLength];
   switch (x)
      {
      case 0x80:
      case 0xC0:
      case 0xE0:
      case 0xF0:
      case 0xF8:
      case 0xFC:
      case 0xFE:
         return 2;
      }
   return 0;
   }

It may be a bit inefficient for small wordlengths, if it is a problem you should spend some time and make it better.

-- modified at 6:57 Monday 3rd September, 2007

The reason I am suggesting a switch statement rather than a loop is that I thought the reason that in C/C++ the case values had to be constants was so that the compiler could order them and implement the switch as a simple binary search, so for N case statements there would be only log2(N) comparisons. I can't easily find a reference for this now - does anyone know if this happens?

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

Russell^'3-Sep-07 1:09

3-Sep-07 1:09

cp9876 wrote:
I can't easily find a reference for this now - does anyone know if this happens?

Try to look the disassembly window opening it to the code you suggested ... Smile | :)

I think that this shortcut is applyed from the compiler only if the number of case is greather then a specified number ... and only if you turn on that optimizations that is probally related with faster applications, but not applyed in small exe file dimension.

Russell

Russell^'3-Sep-07 0:26

3-Sep-07 0:26

In this case I think that the better solution is a general solution...so a loop like

tmpword=word;
for(i=0;i<wordlength;i++){
  if(tmpword == 1) return 1;
  if(tmpword & 1 ) tmpword >>=1;
  else break;
}

tmpword=word;
for(i=0;i<wordlength;i++){
  if(tmpword == 0x80) return 2;
  if(tmpword & 0x80 ) tmpword <<=1;
  else break;
}

return 0;

or somethig similar to this
(I haven't tested the code...it is only an idea of what I'm meaning above... Unsure | :~

)

Russell

rihdus3-Sep-07 2:06

rihdus

3-Sep-07 2:06

try this vb code:

Private Function GetWordStatus(ByVal word As Integer) As Integer

Dim significantLength As Integer = (word & "").Length
'Calculate significant Length of number
Dim temp As Integer
temp = (2 ^ significantLength) - 1

If Convert.ToInt64(word, 2) = temp Then
Return 1
Else
Dim cntr As Integer
temp = 2 ^ (significantLength - 1)
cntr = (significantLength - 1)
While cntr > 1

If Convert.ToInt64(word, 2) = temp Then
Return 2
Else
temp += 2 ^ (cntr - 1)
End If
cntr = cntr - 1

End While
End If
' Return 0

End Function

Its not the best but an alternative Smile | :)

Any systematic work reflects its significance for a long time. So let's discuss the best...

Luc Pattyn3-Sep-07 5:37

Luc Pattyn

3-Sep-07 5:37

Hi,

it is much simpler than that.

one spec is missing: what if input is zero ?

THEORY (assume unsigned integers)

1.
if all zeroes followed by all ones, then one more becomes a power of two

2.
if all ones followed by all zeroes, then bitwise complement reverts to first case

3.
a power of two has just one bit set; it can be tested in one line:

if (( x & (-x) )==x) then either x = zero or x = power of 2    !!!

CODE

if (x==0) return whatever you think is appropriate
if ((x&(-x))==x) return 1;
x=~x;
if ((x&(-x)==x) return 2;
return 3;

Luc Pattyn [Forum Guidelines] [My Articles]

Russell^'3-Sep-07 5:46

3-Sep-07 5:46

You won

Russell

cp98763-Sep-07 19:55

cp9876

3-Sep-07 19:55

I knew there would be a clever bit twiddling answer to this - very neat!

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

polyhedron4-Sep-07 16:47

polyhedron

4-Sep-07 16:47

fn(WORD w)
{
WORD mark=0x8000;
if(w&mark)
{
mark >>= 1;
while( (w&mark) && mark )
mark >>= 1;
if(mark==0)//w must = 0xffff,return 1 or 2
return 2;//also can return 1
if(w&(mark-1))
return 0;
else
return 2;
}
else
{
mark >>= 1;
while( ((w&mark)==0) && mark )
mark >>= 1;

if( (w&(mark-1))==(mark-1) )
return 1;
else
return 0;
}
}

which one would be faster?

Nelek12-Sep-07 5:05

Nelek

12-Sep-07 5:05

Hi,

what about...

int GetWordStatus(int word,int word length)
{
if (word == 0)
return 0;

int nHigh = word / pow (2, word_length);
int nLow = word % pow (2, word_length);

if (nHigh > nLow)
return 1;

else if (nHigh < nLow)
return 2;

else
return 3;
}

Greetings.

--------
M.D.V.

If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?

Help me to understand what I'm saying, and I'll explain it better to you

Wink | ;)

Mushtaque Nizamani2-Sep-07 21:30

Mushtaque Nizamani

2-Sep-07 21:30

There are two sets
one set has ten thousands elements
other set has 30 element

Which loop would be the faster

for(i = 0; i < sizeoffirstset(10000); i++)
{
for (j=0; i < sizeofsecondset(20); j++)
{
if(set1[i] == set2[j])
//do some thing
}
}

for(i = 0; i < sizeofsecondset(20); i++)
{
for (j=0; i < sizeoffirstset(10000); j++)
{
if(set2[i] == set1[j])
//do some thing
}
}

Best Regards,
Mushq

Mushtaque Ahmed Nizamani
Software Engineer
Ultimus Pakistan

Michael Dunn2-Sep-07 21:40

Michael Dunn

2-Sep-07 21:40

Both are doing the same operations, just in a different order.

--Mike--
Visual C++ MVP Cool | :cool:

LINKS~! Ericahist | PimpFish | CP SearchBar v3.0 | C++ Forum FAQ

I work for Keyser Söze

Russell^'2-Sep-07 22:03

2-Sep-07 22:03

Mushq wrote:
sizeofsecondset(20)...sizeoffirstset(10000)

const UINT Sizeoffirstset =sizeoffirstset (10000); //this can help the compiler
const UINT Sizeofsecondset=sizeofsecondset(20);
for(i = 0; i < Sizeofsecondset; i++)
{
for (j=0; j < Sizeoffirstset; j++)
{
if(set2[i] == set1[j])
//do some thing
}
}

I'm looking for differences, I see only that the initialization j=0 is computed Sizeofsecondset times ... so let Sizeofsecondset be the smaller number.
Smile | :)

Russell

Russell^'2-Sep-07 22:05

2-Sep-07 22:05

Mushq wrote:
for(i = 0; i < sizeoffirstset(10000); i++)
{
for (j=0; i < sizeofsecondset(20); j++)

Ahahah

faster yes .... but to go where? Laugh | :laugh:

Russell

rihdus2-Sep-07 22:21

rihdus

2-Sep-07 22:21

First one is faster and because of internal smaller array.
run following code in VB:

Dim i, j As Integer
Dim strArr1(10000) As String
Dim strArr2(20) As String
For i = 0 To 10000
strArr1(i) = i & ""
Next
For i = 0 To 20
strArr2(i) = i * i * i & ""
Next
Response.Write(DateTime.Now.Millisecond.ToString())
For i = 0 To 10000
For j = 0 To 20
If (strArr1(i) = strArr2(j)) Then
Response.Write("
Hello" & strArr1(i) & strArr2(j))
End If
Next
Next
Response.Write(DateTime.Now.Millisecond.ToString())
For i = 0 To 20
For j = 0 To 10000
If (strArr2(i) = strArr1(j)) Then
Response.Write("
Hello " & strArr2(i) & strArr1(j))
End If
Next
Next
Response.Write(DateTime.Now.Millisecond.ToString())

Any systematic work reflects its significance for a long time. So let's discuss the best...

Russell^'2-Sep-07 22:36

2-Sep-07 22:36

Yes: finally the best way to find out who is the faster is use ... the clock Laugh | :laugh:

Russell

Luc Pattyn3-Sep-07 5:43

Luc Pattyn

3-Sep-07 5:43

Sure, measuring is good, smart measuring is even better.

if you have two alternatives that are likely to be almost equal, whichever you try first
will take longer, due to different starting conditions (maybe code needs to be JITted,
probably data needs to be loaded in memory and/or will be loaded in cache, etc).

Remedy: put everything in a for loop, and run a few passes; ignore the first pass,
take the average (or the best time!) of the remaining passes.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Mushtaque Nizamani2-Sep-07 22:51

Mushtaque Nizamani

2-Sep-07 22:51

Thanks for reply.

rihdus wrote:
First one is faster and because of internal smaller array.

can you please explain a bit more.

Best Regards,
Mushq

Mushtaque Ahmed Nizamani
Software Engineer
Ultimus Pakistan