|
I saw a PBS show about this very thing over a year ago. I've been wondering how much more advanced we would be right now if that knowledge had passed down through the ages?
|
|
|
|
|
Unfortunately, we'll never know. But in this case, it wasn't religion's fault. 
|
|
|
|
|
Is there an efficient algorithm to fill memory with an arbitrary pattern?
void memoryfill( void* target, char* pattern, size_t patlen, size_t numRepeats )
{
if( 1 == patlen ) memset(target, *pattern, numRepeats);
else ???
}I came up with something that makes 2*log(numRepeats) calls to memcpy(), but figured this must be a standard thing to do, and there is probably a good algorithm (better than mine?) already out there. I couldn't find anything on CodeProject, or on Google.
David
|
|
|
|
|
|
You can use destructive overlap to write your fill pattern as fast as your CPU can go. Here's the algorithm:
1. Copy one instance of the pattern to target.
2. Copy memory from target to (target + patlen) with length (numRepeats - 1) * patlen. (This is one function call.)
I believe this is the most efficient algorithm possible. The implementation of memcpy will probably be more efficient than anything you could write in a higher-level language. Also you're copying from addresses you just wrote to, so they'll already be in the cache. This lets the CPU avoid getting these bytes from (relatively) slow external memory chips. This algorithm should fly like the wind!
|
|
|
|
|
IF (a few critical things...) then I think you're right. I think your algorithm will work really really good. I'm working on other things, and don't really want to write a timing test, but I believe you're probably right about it being the fastest possible algorithm.
Now for the critical things:
IF memcpy copies from the end of the array instead of from the base, this algorithm won't work at all. Depending on how it computes the target (if copying from the end), it'll either copy garbage until it finally hits the first pattern, and then make one good copy of it, or it'll make one good copy first, then cause a GPF by attempting to overwrite memory to the left of the src. Here's a quote from "STANDARD C" by P.J. Plauger and Jim Brodie regarding memcpy: "The elements of the array can be accessed and stored in any order." It could even start in the middle of the array if that favors the target environment.
I suppose one could bracket the code with #if's, assuming one could absolutely determine how memcpy worked; and guarantee that it never changes it's mind depending on any number of things.
The other alternative is to simply write the algorithm myself in C. This way I could guarantee copying from the base of the array instead of from the end. But, as you point out, memcpy is highly tuned for the machine architecture, and my "roll your own" isn't going to work as well.
Thanks a lot anyway. I really appreciate the thoughts. Maybe your idea will come in handy in some of my future projects. It was a really good idea.
David
|
|
|
|
|
After thinking a bit more about it, I realized the stuff about the GPF is probably not correct. It would just copy garbage.
As I think thru things, I try to document them so I (or someone else) won't come back later on and try to improve on the code without throughly thinking things thru. Based on your suggestion, I've added the following comments to my memoryFill() function.
void memoryFill( void* target, char* pattern, size_t ptrnlen, size_t numRepeats )
{
char* trgt = (char*)target;
...
...
}
David
|
|
|
|
|
Hello,
is there any known algorithm to check how different are two files,
i mean to check how big is a difference between two files?
regards
termal
|
|
|
|
|
Google on diff algorithms, there are a couple of articles on CP on this - search for diff
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."
|
|
|
|
|
Hello,
thanks very much for answer!
regards
termal
|
|
|
|
|
You don't need an algorithm to check the difference in size between two files. You can just read each file one line at a time and count the bytes of each or if the files are small get a byte array of the files and then comapare the sizes of the arrays.
There are 10 types of people in the world, those who understand binary and those who dont.
|
|
|
|
|
smyers wrote: You don't need an algorithm to check the difference in size between two files. You can just read each file one line at a time and count the bytes of each or if the files are small get a byte array of the files and then comapare the sizes of the arrays.
Why would I need to do that? Any language should include calls to return size of a file...
|
|
|
|
|
I googled it, you can use the FileInfo.Length property...sorry
There are 10 types of people in the world, those who understand binary and those who dont.
|
|
|
|
|
in C you can use like this,to find the size of the file
_chdir(path);//path of your required file's folder
struct_finddata_t fileinfo;
long k=_findfirst("*.*",&fileinfo);
if(fileinfo.name=filename)//filename of your file
{
//here, you can find the filesize in the fileinfo structure.
}
otherwise, findnext();
and repeat.
Suggestion to the members:
prefix your main thread subject with [SOLVED] if it is solved.
chandu.
|
|
|
|
|
Check out www.groganenterpriseservices.com/textcompare. I use this facility to compare two MSINFO32 export files. Size is limited to 5k lines for web access. It calculates diffs using CRC's and runs like a bat. If you need the source or have larger files and would like to use it let me know. marty redondowa com
Been there, done that, forgot again.
|
|
|
|
|
Hello, I have considered doing following project:
Imagine that you have simple graphics (like some schematics, logo, etc). I'd like to investigate some other approaches to saving the image like traditional bitmap/vector files.
It would use some kind of advanced algorithms to generate set of graphical operations (draw line/shape/curve, fill shape, draw text somewhere) that would be drawn to some bitmap. The program would then evaluate how much the generated image look like the original (like fitness function in GA), I mean, evaluate many solutions, find the best ones, combine/mutate them in some way to produce better results in the next generation.
It would not be saving the image in the true sense of word, it would be more like finding algorithm on how to recreate it with the best precision using elementary graphical operations. Maybe it would be useless, maybe not.
My question is, *how* should I start? I read something on the topic of genetic algorithms, but most of the articles dealt with using binary string (genes) for representing the operations (but wouldn't it be too long to encode many (tens, hundreds) graphical operations with parameters?) I mean, if we had about hundred operations (8-bit identifier) with average of four 16-bit parameters, it would be about 100*8+100*4*16=7200 bits of information to combine, mutate and eventually, evaluate.
I know it will be painfully slow, to have some kind of fitness evaluation function that would need to draw image from the "genes", but this would be a research project. I am just wondering if something like this is possible (I think it could be), and if yes, someone could please point me in the right direction to start.
thanks,
Juraj
|
|
|
|
|
G'day Juraj,
Juraj Borza wrote: The program would then evaluate how much the generated image look like the original (like fitness function in GA), I mean, evaluate many solutions, find the best ones, combine/mutate them in some way to produce better results in the next generation.
You might take a look at Bezier curves and spline functions. In the early nineties i saw a demo of a graph of a teapot on a Unix workstation. The image was entirely generated by means of splines. The light reflection is very realistic, since the first order derivatives of the splines are continuous, at the edges as well.
Regards,
Stan
|
|
|
|
|
It sounds to me like you are conceptually describing a compression algorithm. But I think you are really looking for a different result. Can you clarify your goal for this algorithm?
Otherwise, I suggest you look at using wavelets to represent discrete sections of the image. The wavelets are easily reconstructed to a reasonable representation of the image. Depending on how you structure them, they can represent it perfectly, or in as much abstraction as you desire.
If you continue to do the same things you always did,
don't be surprised if you get the same results you always got.
|
|
|
|
|
Your instincts are correct: This is feasible and isn't that hard. You need to define your "genes" and mutation operators. Genes will be more than single bits, and you may want to restrict recombination to gene boundaries.
Traditional genetic algorithms use a fixed number of genes, but you will want a variable number, to represent different approachs to drawing the image. Google "genetic programming" to see genetic-algorithm examples with variable-sized genotypes.
There's already a similar method for compressing images called "Fractal Compression", in which fractals are combined to mimic the image being compressed. It's more systematic than a genetic algorithm, and compression ratios on the order of 10,000 to 1 have been reported.
|
|
|
|
|
Suppose I have an image of a region of earth of arbitrary size and I have Lat/Long from two points on the map is there a simple formula for converting a given pixel to a Lat/Long that takes into account the curvature of Earth? Assume perfect lens and that the map is of such a scale and size that a given pixel distance will be the same across the image.
And yes, I know, if I could afford ARC/GIS it will do it for me.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway
|
|
|
|
|
Ennis Ray Lynch, Jr. wrote: Suppose I have an image of a region of earth of arbitrary size and I have Lat/Long from two points on the map is there a simple formula for converting a given pixel to a Lat/Long that takes into account the curvature of Earth? Assume perfect lens and that the map is of such a scale and size that a given pixel distance will be the same across the image.
Not positive from how the question is asked (by "image of a region" do you mean a rendering of the earth in perspective, ortho, a map projection?), but here is is the lowdown:
If you have a perspective image of the earth, find the local xyz coordinates, convert to ECEF, then to lat,long, alt.
If you have an ortho image, again depending on your projection, you get a local coordinate and convert through.
if you have a map projection, use the appropriate conversion to/from to get to ECEF and/or directly to lat/long.
http://www.gdal.org/[^]
http://www.maptools.org/[^]
http://www.bluemarblegeo.com/products/geocalc.php[^]
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
I have a picture taken of the ground of which I know a few lat/long coords. I would like to move the mouse over the picture and have the mouse x,y translated into lat/long.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway
|
|
|
|
|
Ennis Ray Lynch, Jr. wrote: I have a picture taken of the ground of which I know a few lat/long coords.
if you don't know the location of the camera, or the projection of the image, you will have to do interpolation estimation based on the deltas between your lat/long points.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
However, interpolation between delta's itself will not work against longitude as the distance between two lines of longitude change based on the latitude. I could break out my trig but I just wanted to know if anyone had a good formula handy.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway
|
|
|
|
|
Ennis Ray Lynch, Jr. wrote: interpolation between delta's itself will not work against longitude as the distance between two lines of longitude change based on the latitude.
that is why they have map projections. GDAL does the Proj.4 conversions between formats. Generally you go through a cartesian system, like Earth Centered Earth Fixed (ECEF). http://en.wikipedia.org/wiki/Geodetic_system[^]
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
