Magnetoresistance (MR) effects are at the heart of modern information technology. However, future progress of giant and tunnelling MR based storage and logic devices is limited by the usable MR ratios of currently about 200% at room-temperature. Colossal MR structures, on the other hand, achieve their high MR ratios of up to 10(6)% only at low temperatures and high magnetic fields. We introduce the extraordinary Hall balance (EHB) and demonstrate room-temperature MR ratios in excess of 31,000%. The new device concept exploits the extraordinary Hall effect in two separated ferromagnetic layers with perpendicular anisotropy in which the Hall voltages can be configured to be carefully balanced or tipped out of balance. Reprogrammable logic and memory is realised using a single EHB element. PACS numbers: 85.75.Nn,85.70.Kh,72.15.Gd,75.60.Ej.