Go to Post Every thing is a hammer except for the screw driver which is a chisel. - BradL [more]
Home
Go Back   Chief Delphi > Technical > Programming
CD-Media   CD-Spy  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
Closed Thread
Thread Tools Rate Thread Display Modes
  #46   Spotlight this post!  
Unread 08-09-2004, 22:51
djcapelis's Avatar
djcapelis djcapelis is offline
Fried Manic Custard
None #0675 (Geeks with Power Tools)
Team Role: Programmer
 
Join Date: May 2003
Rookie Year: 2001
Location: Rohnert Park, CA
Posts: 129
djcapelis will become famous soon enoughdjcapelis will become famous soon enough
Send a message via ICQ to djcapelis Send a message via AIM to djcapelis Send a message via Yahoo to djcapelis
Re: New compression method

Look, the math is quite simple on why this doesn't work...

Let me reduce it down for 4 bits to make things simple.

Let's say I make a program and claim that it can compress things to 4 bits. That means there are 16 possible files. Only 16 possible files. It is mathematically impossible to compress more than 16 files into 4 bits with the same procedure, no matter how many times you run it. (In the case of recursiveness you'd have to keep track of how many times which would immediately add to the file size.) This same concept applies when you make a claim to be able to compress any 1 megabyte file into 500 bytes.

It is simply absurd. Compression algorithms only work because they are good at finding patterns and taking patterned data and manipulating it. This is why you will almost never be able to compress random data.

Thanks for playing, hit the books and come back with something that's possible.
__________________
"I have more friends than enemies, I'm working to resolve the issue."
  #47   Spotlight this post!  
Unread 08-09-2004, 23:21
FizMan's Avatar
FizMan FizMan is offline
aboot, eh?
AKA: Chris Sinclair
#0783 (Mobotics)
Team Role: Alumni
 
Join Date: Feb 2004
Location: Toronto, Canada
Posts: 102
FizMan will become famous soon enough
Send a message via AIM to FizMan Send a message via MSN to FizMan
Re: New compression method

I'd be interested to test out the decompressor as well. My email is fizixman@vgamp.com so let me know when... and send out a non-disclosure agreement or something or other if you're worried.


EDIT: Let's not forget that "Jack" here on Chiefdelphi is his friend... so Aalfabob, you should get together with Jack and show him your program working, and then you can testify Jack
__________________
Joules per second! Watt? Joules per second! Watt? Jouls per second! Watt?

Last edited by FizMan : 08-09-2004 at 23:48.
  #48   Spotlight this post!  
Unread 09-09-2004, 00:23
MikeDubreuil's Avatar
MikeDubreuil MikeDubreuil is offline
Carpe diem
FRC #0125 (Nu-Trons)
Team Role: Engineer
 
Join Date: Jan 2003
Rookie Year: 1999
Location: Boston, MA
Posts: 967
MikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond reputeMikeDubreuil has a reputation beyond repute
Send a message via AIM to MikeDubreuil
Re: New compression method

I'd be interested in seeing this work as well. You can contact me at DubreuilM@wit.edu.

I'm most interested in seeing how the test will handle a 5MB dump from /dev/random on a UNIX machine.
__________________
"FIRST is like bling bling for the brain." - Woodie Flowers
  #49   Spotlight this post!  
Unread 09-09-2004, 00:27
ErichKeane ErichKeane is offline
Registered User
FRC #3210
Team Role: Mentor
 
Join Date: Nov 2003
Rookie Year: 2004
Location: Hillsboro, OR
Posts: 113
ErichKeane is just really niceErichKeane is just really niceErichKeane is just really niceErichKeane is just really niceErichKeane is just really nice
Send a message via AIM to ErichKeane
Re: New compression method

Mike!! I had no idea anyone else from here went to WIT! Im a freshman on campus, tudbury mid, such a small world eh?

anyway, i think this is going to be one of those situations where someone has somethign solved in their mind supposedly, but then just "forgets" one small, simple thing that screws up the whole boat.
  #50   Spotlight this post!  
Unread 09-09-2004, 01:03
Elgin Clock's Avatar
Elgin Clock Elgin Clock is offline
updates this status less than FB!
AKA: the one who "will break into your thoughts..."
FRC #0237 (Black Magic)
Team Role: Mentor
 
Join Date: May 2001
Rookie Year: 2001
Location: H20-Town, Connecticut
Posts: 7,773
Elgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond reputeElgin Clock has a reputation beyond repute
Send a message via AIM to Elgin Clock
Re: New compression method

Quote:
Originally Posted by ErichKeane
anyway, i think this is going to be one of those situations where someone has somethign solved in their mind supposedly, but then just "forgets" one small, simple thing that screws up the whole boat.
If that is the case, then I hope both sides of the debate that this has turned into graciously apologize to each other, and no one says "See, I told you it couldn't be done" or whatever.

I am for the most part skeptical till I see something work in front of me, but love to dream that it could.

Don't rain on this person's parade, until you absolutely see it not work (and even then, add ways that it may be able to work).



By the way, I have come up with a great idea for a perpetual motion machine, but until I can get a prototype made, I won't reveal my new idea.

One reason being that I don't want anyone else to take the credit for it, but the second reason is that if it does not work in real life like it does on paper, then I don't want the kind of responses that Aalfabob is recieving and the embarassment of letting myself down in public.

Remember those two words people. Gracious Professionalism.
Make your grandma's proud. Don't blindly say that something will or will not work until you see the proof that it does or does not.
__________________
The influence of many leads to the individuality of one. - E.C.C. (That's me!!)

  #51   Spotlight this post!  
Unread 09-09-2004, 10:09
FizMan's Avatar
FizMan FizMan is offline
aboot, eh?
AKA: Chris Sinclair
#0783 (Mobotics)
Team Role: Alumni
 
Join Date: Feb 2004
Location: Toronto, Canada
Posts: 102
FizMan will become famous soon enough
Send a message via AIM to FizMan Send a message via MSN to FizMan
Re: New compression method

lolk, I love trying to invent perpetual motion machines! If you ever want someone to take a fresh look at your machine (because I find, that it often times will point out that little flaw that is so obvious... yet, so hidden) make me sign a confidentiality agreement or something.

Though lol, sometimes I feel bad for saying, "Umm... you realize blah blah blah so it won't work..." ;_;
__________________
Joules per second! Watt? Joules per second! Watt? Jouls per second! Watt?
  #52   Spotlight this post!  
Unread 09-09-2004, 15:35
Aalfabob's Avatar
Aalfabob Aalfabob is offline
Registered User
#0201 (FEDS)
 
Join Date: Sep 2004
Rookie Year: 2004
Location: Rochester, MI
Posts: 27
Aalfabob is on a distinguished road
Send a message via AIM to Aalfabob
Re: New compression method

Alright heres an update on how build 5 is going:
I was going to try a new method I had came up with about a day ago cause I thought it would be a little better. After running a few tests on it, I found out that only some files ran better then the past method, and sometimes the files even got larger. I havent finished fully testing this program because when a file is being changed through a pass, it ends up with a totally different make-up inside of it which means that it could actually regain the lost bytes and compress below the original file. Although the 1st method is a little more complex, I should still be able to meet that dead line I gave before if anything doesnt 'pop-up' (Life stuff). And if something does happen, it wont delay the test by much. Im putting as much time as I can into programming it right now and dont have work for the next couple of days.

I am taking a break from that method and moving back into the first which I thought was going to be very slow, but I redesigned most of it to make it actually faster then the new method. Ive checked a couple of the files after a couple of runs by hand to see if the data is coming out right and everything seems fine. Thats about it for now.

edit - Some good news is though that I had finished the compressor before for the first method so I can basically copy most of the functions over and with some changes in file set up it should be good to go.
  #53   Spotlight this post!  
Unread 09-09-2004, 15:38
Fulcrum2000 Fulcrum2000 is offline
Registered User
no team
 
Join Date: Sep 2004
Location: Netherlands
Posts: 7
Fulcrum2000 can only hope to improve
Re: New compression method

Quote:
Originally Posted by Aalfabob
Ive checked a couple of the files after a couple of runs by hand to see if the data is coming out right and everything seems fine. Thats about it for now.
Sounds good, my 10000 dollar offer is still valid...
  #54   Spotlight this post!  
Unread 09-09-2004, 18:59
FizMan's Avatar
FizMan FizMan is offline
aboot, eh?
AKA: Chris Sinclair
#0783 (Mobotics)
Team Role: Alumni
 
Join Date: Feb 2004
Location: Toronto, Canada
Posts: 102
FizMan will become famous soon enough
Send a message via AIM to FizMan Send a message via MSN to FizMan
Re: New compression method

So Aalfa, do you take certified cheques/money order or have paypal? roffle
__________________
Joules per second! Watt? Joules per second! Watt? Jouls per second! Watt?
  #55   Spotlight this post!  
Unread 09-09-2004, 23:20
Aalfabob's Avatar
Aalfabob Aalfabob is offline
Registered User
#0201 (FEDS)
 
Join Date: Sep 2004
Rookie Year: 2004
Location: Rochester, MI
Posts: 27
Aalfabob is on a distinguished road
Send a message via AIM to Aalfabob
Re: New compression method

Please correct me if im worng but I think this can help prove it a little better:

So say I have 512 bytes of data im compressing. This can contain 3.74 * 10^693 different combinations correct? So say I add a byte to that (513 Bytes), the combinations that creates are 6.16 * 10^693 or twice as much.

So say I have one byte as a header that can count the amount of times that data has been compressed. So that header can hold 256 values. So depending on which way those bytes come out (3.74 * 10^693), the counter can hold 256 different values so wouldnt adding that 1 byte for counting actually make the file have 9.57 * 10^695 combinations (256 * (3.74 * 10^693))? Now this is alot more combinations avaliable for the same amount of data. Hopefully I did that right.

Data:
512 byte combinations = 3.74 * 10^693
513 byte combinations = 6.16 * 10^693
513 with one byte being a counter = 9.57 * 10^695

If im correct i think that this can prove that that many pieces of randomly generated code can fit in that space. And plus im using a 2 byte main header which can contain 65536 runs.
  #56   Spotlight this post!  
Unread 09-09-2004, 23:48
MrToast's Avatar
MrToast MrToast is offline
I named Greg Needel's cat!
AKA: Dave DeLong
no team (Rhode Warriors)
Team Role: Alumni
 
Join Date: Mar 2004
Rookie Year: 2004
Location: RI, now UT
Posts: 326
MrToast has much to be proud ofMrToast has much to be proud ofMrToast has much to be proud ofMrToast has much to be proud ofMrToast has much to be proud ofMrToast has much to be proud ofMrToast has much to be proud ofMrToast has much to be proud of
Send a message via AIM to MrToast
Re: New compression method

Any chance of a Mac OS X compile? Interestingly enough, I'm also collaborating with a friend in producing a new compression scheme that uses recursive compression. Don't ask me about it, though. I'm just building the interface.

mrtoast@gmail.com

MrToast

[edit] 121st post! Go Rhode Warriors![/edit]
__________________
(#121, 2004) Archimedes semi-finalists with 237 and 386! I had an awesome time guys, and thanks for the hat!
(#121, 2004) BC5 semi-finalists with 190 and 1027! Awesome time! We went further than I thought we could! Thanks for all your help w/ our transmission!
(#121, 2005) Galileo quarter-finalists with 47 and 203! Thanks for all your support through the stress!
------------------------------
If it moves and it shouldn't, use duct tape.
If it doesn't move and it should, use WD-40
------------------------------
"It'll all work out in the end, and if it doesn't, it's not the end." - Jeff Bullock
  #57   Spotlight this post!  
Unread 10-09-2004, 00:03
rbayer's Avatar Unsung FIRST Hero
rbayer rbayer is offline
Blood, Sweat, and Code
no team (Teamless Orphan)
 
Join Date: Mar 2002
Rookie Year: 2001
Location: Minnetonka, MN
Posts: 1,087
rbayer is a glorious beacon of lightrbayer is a glorious beacon of lightrbayer is a glorious beacon of lightrbayer is a glorious beacon of lightrbayer is a glorious beacon of light
Send a message via AIM to rbayer
Re: New compression method

Quote:
Originally Posted by Aalfabob
Please correct me if im worng but I think this can help prove it a little better:

So say I have 512 bytes of data im compressing. This can contain 3.74 * 10^693 different combinations correct? So say I add a byte to that (513 Bytes), the combinations that creates are 6.16 * 10^693 or twice as much.

So say I have one byte as a header that can count the amount of times that data has been compressed. So that header can hold 256 values. So depending on which way those bytes come out (3.74 * 10^693), the counter can hold 256 different values so wouldnt adding that 1 byte for counting actually make the file have 9.57 * 10^695 combinations (256 * (3.74 * 10^693))? Now this is alot more combinations avaliable for the same amount of data. Hopefully I did that right.

Data:
512 byte combinations = 3.74 * 10^693
513 byte combinations = 6.16 * 10^693
513 with one byte being a counter = 9.57 * 10^695

If im correct i think that this can prove that that many pieces of randomly generated code can fit in that space. And plus im using a 2 byte main header which can contain 65536 runs.
It doesn't matter _what_ is stored in that extra byte. It's still just 8 bits. Adding 1 more byte, regardless of contents, always gives you 256 (that's 2^8) times as many possible combination. A bit, is a bit, is a bit, regardless of how your program interprets it. Also, keep in mind that 2^4096 (4096 is the number of bits in 512 bytes, so 2^4096 is the number of different possible 512-byte files) is still _astronomically_ smaller than 2^8388608, the number of different possible 1MB file. I really can't stress this enough: it has been _proven_ that you cannot compress every file of a given size down to a file smaller than the original (even if only by 1 bit). This has been PROVEN. Trying to do it is basically the same as trying to find an O(n) sorting algorithm (proven to be impossible) or trying to solve the halting problem (also proven impossible). While you're at it, why don't you find an integer solution to x^3 + y^3 = z^3.

Also, I _love_ math and arguing about math, etc, but _please_ use 2^x instead of 10. With binary stuff it makes it SO much easier to understand what's actually going on.

Rob
__________________
New C-based RoboEmu2 (code simulator) available at: http://www.robbayer.com/software.php
  #58   Spotlight this post!  
Unread 10-09-2004, 00:20
Max Lobovsky's Avatar
Max Lobovsky Max Lobovsky is offline
Fold em oval!
FRC #1257 (Parallel Universe)
Team Role: College Student
 
Join Date: Jan 2004
Rookie Year: 2004
Location: Scotch Plains, NJ
Posts: 1,026
Max Lobovsky has a brilliant futureMax Lobovsky has a brilliant futureMax Lobovsky has a brilliant futureMax Lobovsky has a brilliant futureMax Lobovsky has a brilliant futureMax Lobovsky has a brilliant futureMax Lobovsky has a brilliant futureMax Lobovsky has a brilliant futureMax Lobovsky has a brilliant futureMax Lobovsky has a brilliant futureMax Lobovsky has a brilliant future
Send a message via AIM to Max Lobovsky
Re: New compression method

Quote:
Originally Posted by Aalfabob
Please correct me if im worng but I think this can help prove it a little better:

So say I have 512 bytes of data im compressing. This can contain 3.74 * 10^693 different combinations correct? So say I add a byte to that (513 Bytes), the combinations that creates are 6.16 * 10^693 or twice as much.

So say I have one byte as a header that can count the amount of times that data has been compressed. So that header can hold 256 values. So depending on which way those bytes come out (3.74 * 10^693), the counter can hold 256 different values so wouldnt adding that 1 byte for counting actually make the file have 9.57 * 10^695 combinations (256 * (3.74 * 10^693))? Now this is alot more combinations avaliable for the same amount of data. Hopefully I did that right.

Data:
512 byte combinations = 3.74 * 10^693
513 byte combinations = 6.16 * 10^693
513 with one byte being a counter = 9.57 * 10^695

If im correct i think that this can prove that that many pieces of randomly generated code can fit in that space. And plus im using a 2 byte main header which can contain 65536 runs.
No, you are not correct, there are 2^8=256 times as many 513 byte sets as 512 byte sets, not twice as many, just as many combinations as a one byte header adds... There really is absolutely no argument, you cannot consistently store a file in a space smaller than that file, otherwise you wouldn't be able to store all possible files...
__________________
Learn, edit, inspire: The FIRSTwiki.
Team 1257


2005 NYC Regional - 2nd seed, Xerox Creativity Award, Autodesk Visualization Award
2005 Chesapeake Regional - Engineering Inspiration Award
2004 Chesapeake Regional - Rookie Inspiration award
2004 NJ Regional - Team Spirit Award
  #59   Spotlight this post!  
Unread 10-09-2004, 10:07
Mark McLeod's Avatar
Mark McLeod Mark McLeod is online now
Just Itinerant
AKA: Hey dad...Father...MARK
FRC #0358 (Robotic Eagles)
Team Role: Engineer
 
Join Date: Mar 2003
Rookie Year: 2002
Location: Hauppauge, Long Island, NY
Posts: 8,725
Mark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond reputeMark McLeod has a reputation beyond repute
Re: New compression method

The judgment might be being made among some of you that the algorithm is automatically a failure since it cannot possibly compress all possible combinations of files to 515 bytes. The algorithm doesn’t have to be equally successful with compressing every class of file, and they don’t all have to be reduced to 515 bytes to be considered successfully compressed. The most “successful” compression technology becomes so by specializing in one class of file or another, e.g., imagery, text, object, and executable files. Our friend here hasn’t yet had the opportunity to run rigorous tests on the wide variety of files within even one class yet to discover the limitations of his algorithm.

This is a learning experience in developing an algorithm. Everyone can help as independent testers, with developing test procedures, mathematical proofs, test sets, critique, etc. Just keep it positive. The mathematical reasoning posted above is very good experience for Aalfabob and for any of us for the type of proof that will be required whenever you develop a commercially viable algorithm.

Don’t be discouraged to uncover shortcomings of your method.
__________________
"Rationality is our distinguishing characteristic - it's what sets us apart from the beasts." - Aristotle

Last edited by Mark McLeod : 10-09-2004 at 11:56.
  #60   Spotlight this post!  
Unread 10-09-2004, 15:09
Aalfabob's Avatar
Aalfabob Aalfabob is offline
Registered User
#0201 (FEDS)
 
Join Date: Sep 2004
Rookie Year: 2004
Location: Rochester, MI
Posts: 27
Aalfabob is on a distinguished road
Send a message via AIM to Aalfabob
Re: New compression method

Isnt the formula combinations = bytes ^ values

so like a 512 byte peice of data ^ 256 possible charactors = 3.742e+693 combinations?

edit - Nm got the wrong formula from someone.

Last edited by Aalfabob : 10-09-2004 at 15:34.
Closed Thread


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Compression Crisis reisser 3D Animation and Competition 9 22-02-2004 11:23
IRI Elimination Round Method D.J. Fluck Off-Season Events 19 23-07-2003 18:56
Scouting method suggestiongs punarhero Scouting 0 26-01-2003 04:27
What is your favorite method for attaching gears to shafts? archiver 2001 13 24-06-2002 04:00
CRYSTAL METHOD CONCERT drksdofthemoon Chit-Chat 7 30-04-2002 16:58


All times are GMT -5. The time now is 13:31.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi