Until recently I didn't even know there existed such a pen-and-paper algorithm resembling long division:

https://xlinux.nist.gov/dads/HTML/cubeRoot.html